# 騎士巡邏

## 路径的个数

• 在一个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]

## 參考資料

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.