# 騎士巡邏

5×5棋盘中的一种开巡逻走法

## 路径的个数

• 在一个8×8的棋盘中，有26,534,728,821,064中有向封闭巡逻路径（相互对称的巡逻路径被视为不同的巡逻路径）。[7][8]
• 6×6的棋盘中，共有9862个闭巡逻。[9]
• 8×8棋盘中开巡逻的个数仍然未知。对于$n\times n$n=1，2……）的棋盘中开巡逻的个数是：
1, 0, 0, 0, 1728, 6637920, 165575218320,……（
• Schwenk证明了对于任何一个m×n（m$\le$n）棋盘都有1或1个以上的闭巡逻，除非满足以下3中情况中的一种或更多。[10]
1. m和n都为奇数
2. m= 1, 2, 4
3. m= 3且n= 4, 6, 8
• Cull和Conrad证明了对于任何一个m×n（m$\le$n且m$\ge$5）棋盘，至少有一个（可能是开巡逻）骑士巡逻路径。[11][6]

## 解决骑士巡逻问题的方法

### Warnsdorff规则

Warnsdorff规则指在所有可走且未经过的方格中，马只可能走这样一个方格：从该方格出发,马能跳的方格数最少；如果可跳的方格数相等，则从当前位置看,方格序号小的优先。依照这一规则往往可以找到一条路径但是并不一定能够成功。

## 參考資料

1. ^ Martin Loebbing; Ingo Wegener. The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams. The Electronic Journal of Combinatorics. 1996, 3 (1): R5. Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532 and this number is repeated in Wegener's 2000 book.
2. ^ Brendan McKay. Knight's Tours on an 8x8 Chessboard. Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 1997.
3. ^ Wegener, I. Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. 2000. ISBN 0-89871-458-3.
4. ^ Standage, 30–31.
5. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30.
6. ^ 6.0 6.1 Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discrete Applied Mathematics. 1994, 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q.
7. ^ Brendan McKay. Knight's Tours on an 8x8 Chessboard. Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 1997.
8. ^ Wegener, I. Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. 2000. ISBN 0-89871-458-3.
9. ^ MathWorldKnight's Tour 的资料，作者：埃里克·韦斯坦因
10. ^ Allen J. Schwenk. Which Rectangular Chessboards Have a Knight’s Tour?. Mathematics Magazine. 1991: 325–332.
11. ^ Cull, P.; De Curtins, J. Knight's Tour Revisited. Fibonacci Quarterly. 1978, 16: 276–285.
12. ^
13. ^ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.