# 騎士巡邏

（重定向自骑士巡逻

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

## 路径的个数

• 在一个8×8的棋盘中，有26,534,728,821,064中有向封闭巡逻路径（相互对称的巡逻路径被视为不同的巡逻路径）。[7][3]
• 6×6的棋盘中，共有9862个闭巡逻。[8]
• 8×8棋盘中开巡逻的个数为19,591,828,170,979,904。对于${\displaystyle n\times n}$n=1，2……）的棋盘中开巡逻的个数是：
1, 0, 0, 0, 1728, 6637920, 165575218320,19591828170979904,……（
• Schwenk证明了，除了以下3種情況外，任何的m×n（m${\displaystyle \leq }$n）棋盘都至少有1个闭巡逻，。[9]
1. m和n都为奇数
2. m= 1, 2, 4
3. m= 3且n= 4, 6, 8
• Cull和Conrad证明了对于任何一个m×n（5${\displaystyle \leq }$m${\displaystyle \leq }$n）棋盘，至少有一个（可能是开巡逻）骑士巡逻路径。[10][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 [2012-12-20]. （原始内容存档于2012-01-22）. 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. （原始内容存档于2012-01-27）.
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. 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 [2014-03-24]. （原始内容存档于2013-09-28）.
8. ^ Weisstein, Eric W. (编). Knight's Tour. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
9. ^ Allen J. Schwenk. Which Rectangular Chessboards Have a Knight’s Tour?. Mathematics Magazine. 1991: 325–332.
10. ^ Cull, P.; De Curtins, J. Knight's Tour Revisited (PDF). Fibonacci Quarterly. 1978, 16: 276–285 [2014-03-24]. （原始内容存档 (PDF)于2016-04-19）.
11. ^
12. ^ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.