如何用「馬走日」走遍 6*6 的棋盤？

12-14

只是一個小遊戲，希望詳細一點解答。

Schwenk[1] 有過證明，在 m × n （m ≤ n）的棋盤上，存在閉遍歷，除非

m 和 n 都是奇數
或者 m = 1,2,4
或者 m = 3 且 n = 4,6,8

Cull 和 Conrad 等[2]則證明了矩形棋盤的短邊大於等於 5 的時候，總存在開遍歷。

[1] Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight』s Tour?". Mathematics Magazine: 325–332.
[2] Cull, P.; De Curtins, J. (1978). "Knight"s Tour Revisited". Fibonacci Quarterly 16: 276–285.

這個問題叫做棋盤遍歷問題,在演算法學上面是經典的回溯法問題.百度"回溯法+棋盤遍歷"即可.
----------------------------------------------------------------------------------------------------------------------------------------
但是本質上這是個圖論問題,騎士的行動棋盤等價於一個圖,給6*6的棋盤編號1-36,1連接9和14,2連接10和13和15...以此類推,最後這個圖是這樣的.

騎士圖有很強的對稱美.標上標號的話....就看不清了.

----------------------------------------------------------------------------------------------------------------------------------------
走遍有兩種理解,第一種是像這樣不要求最後一步接第一步,圖論上也就是個求哈密頓路徑問題.

//Mathematica繪圖代碼 g = KnightTourGraph[6, 6]; path = FindHamiltonianPath[g]; checkerboard = ArrayPlot[Table[Mod[j + i, 2], {i, 6}, {j, 6}], ColorRules -&> {1 -&> RGBColor[0, .55, .77], 0 -&> RGBColor[.67, .9, .99]}, Frame -&> False, DataRange -&> {{1, 6}, {1, 6}}]; Show[{checkerboard, HighlightGraph[g, PathGraph[path], GraphHighlightStyle -&> "DehighlightHide", EdgeStyle -&> Directive[Thick, Red]]}]

這個的解特別特別多,我也不知道有多少個.
-------------------------------------------------------------------------------------------------------------------------------------
第二種理解就是最後一步和初始位置重合,也就是哈密頓迴路問題

//Mathematica繪圖代碼 g = KnightTourGraph[6, 6]; cycle = First[FindHamiltonianCycle[g]]; checkerboard = ArrayPlot[Table[Mod[j + i, 2], {i, 6}, {j, 6}], ColorRules -&> {1 -&> RGBColor[0, .55, .77], 0 -&> RGBColor[.67, .9, .99]}, Frame -&> False, DataRange -&> {{1, 6}, {1, 6}}]; Show[{checkerboard, HighlightGraph[g, PathGraph[cycle], GraphHighlightStyle -&> "DehighlightHide", EdgeStyle -&> Directive[Thick, Red]]}]

這個解法少一些,不過也有9862種走法,沒法一一給您過目了.
我這還有別的棋盤遍歷問題的研究.簡單棋盤遍歷

我寫了一個c++程序去解，以下是結果，從左上角開始記為1（步數），然後第2步到達的位置記為2，以此類推。
01 12 21 28 07 10
22 29 08 11 20 27
13 02 23 04 09 06
30 35 32 17 26 19
33 14 03 24 05 16
36 31 34 15 18 25
如果需要程序，歡迎詢問。

無代碼！無真相！放碼過來！