棋盤上的路徑 – 2
在本週謎題「棋盤上的路徑 - 1」中,我們探討了從給定點出發,在棋盤上何時可以找到一條路徑,這條路徑能夠訪問棋盤上的每一個方格。從黑點出發,第一個 3×4 的棋盤存在這樣的路徑,而第二個 3×5 的棋盤則不存在。

對於這個謎題,我們既有起點也有終點,我們需要問的是,是否存在一條路徑,從一個點開始,恰好訪問每個點一次,最終到達另一個點。

的挑戰
對於這兩個棋盤,找出哪些起始位置和結束位置之間存在一條路徑,該路徑能夠遍歷棋盤上的每個方格一次,哪些不存在這樣的路徑。它們的差別是什麼?

勘探
製作一些其他尺寸的棋盤,並嘗試不同的起始位置。你覺得怎麼樣?
你有沒有發現哪些起始位置在每塊棋盤上都比較有效?
筆記
挑戰與探索
在「棋盤上的路徑 - 1」中,我們看到,當沿著路徑移動時,路徑上的顏色序列會交替變化。
正如我們在先前的謎題中看到的,對於偶數格棋盤,例如 3×4 的棋盤,我們必須以與起始顏色相反的顏色結束。對於奇數格棋盤,例如 3×5 的棋盤,我們必須以棋盤某個角落的顏色開始和結束。
這就引出了一個問題──如果我們遵守這些規則,那就夠了嗎?
分析這個問題的一種方法是確定其中一個點的位置,然後查看所有有效路徑的終點。我們可以利用鏡像對稱性(沿著棋盤中心向一個方向或另一個方向翻轉)來減少需要考慮的情況數量。以下是兩個棋盤的結果。紅點是固定的起點,黑點是有效終點的位置。

如您所見,大多數佈局都能成功。失敗的佈局並非顏色交替困難,而是被困在角落。這種限制問題在只有兩行的棋盤上特別突出。我認為,對於四行或更多行的棋盤,這種限制問題就會消失。