大馬小馬走天下
有個經典的騎士巡邏問題 : 騎士用馬步移動,每個格子至多走一次,試圖找出最多步。我們定義2x3的矩形方格圖中走對角線為大馬步,2x2的方格中走對角線為小馬步。依照大馬步、小馬步輪流交錯走,我們發現 : 若指定特殊起始點,在(偶數m) x (偶數n)的矩形中可以走完所有的格子。若騎士能將格子走完,本質上非常類似漢米爾頓路徑。其它無交錯的走法(如連續大馬步或連續小馬步),我們也找出最多步的一般式。本作品的價值在於擴充馬步為大馬步與小馬步,推廣正方形為任意比例的矩形,並用深度優先搜索(Depth First Search,以下簡稱DFS)驗証結果。關鍵論証在於著色法與DFS ,若騎士無法走完,著色法能証明步數的最大值,DFS能讀完圖中所有資訊。結論的一般式紀錄於後。