騎士巡邏

维基百科,自由的百科全书
跳转至: 导航搜索
一种开巡逻走法
5×5棋盘中的一种开巡逻走法

騎士巡邏英语Knight's tour)是指在按照国际象棋骑士的规定走法走遍整个棋盘的每一个方格,而且每个网格只能夠经过一次。假若騎士能夠從走回到最初位置,則稱此巡邏為「封閉巡邏」,否則,稱為「開巡邏」。對於8*8棋盤,一共有26,534,728,821,064種封閉巡邏,但是到底有多少種開巡邏仍然未知。[1][2][3]

由骑士巡逻引申出了一个著名的数学问题 :骑士巡逻问题--找出所有的骑士巡逻路径。编写一个程序来找出骑士巡逻路径经常在计算机系的学生的练习中出现。骑士巡逻问题的变种包括各种尺寸的棋盘甚至非正方形的棋盘。

历史[编辑]

土耳其行棋傀儡执行的骑士巡逻。由于其路线是一条闭路,因此从棋盘上任何一点开始都能完成巡逻。[4]

已知的最早的骑士巡逻问题可以追溯到九世紀的古印度恰圖蘭卡[5]

欧拉是最早研究骑士巡逻的数学家中的一员,而H. C. von Warnsdorff在1823年提出了第一个系统化解决骑士巡逻问题的方法--Warnsdorff规则。

在20世纪,一批乌力波英语Oulipo的作家将这个问题用在了其它的地方。最明显的例子:乔治·佩雷克英语Georges Perec的小说Life: A User's Manual英语的章节顺序就是按照10×10棋盘的骑士巡逻路径来编排的。在2010年国际象棋世界冠军对抗赛的第六场比赛中,棋手阿南德连续13次移动骑士(使用了两个骑士),在线评论员打趣地说阿南德试图在游戏过程中解决了骑士巡逻问题。

骑士巡逻问题的实质[编辑]

骑士巡逻图展现了所有可能的骑士巡逻路径,节点上的数字表示在这个节点上骑士可能路径的个数

骑士巡逻问题实际上是哈密顿路径问题的一种特殊形式,寻找骑士巡逻的闭巡逻路径的个数实际上也是哈密顿循环问题的一种特殊形式。但是和一般的哈密顿路径问题不同,骑士巡逻问题可以在线性时间内解决。[6]

路径的个数[编辑]

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

解决骑士巡逻问题的方法[编辑]

利用人工神经网络的方法在24 × 24的棋盘中寻找到的一条闭巡逻。

借助计算机的帮助,人们已经发现了很多种寻找骑士巡逻路径的方法。其中一部分依靠一些计算机算法,而另外一些则依靠启发法

穷举法[编辑]

穷举法来寻找骑士巡逻路径适用于格数较小的棋盘,因为当方格数过多时,可能的路径过多。例如,8×8棋盘中大约有4×10^51种可能的路径。[12]如此大的运算量已经超出了现代计算机的运算能力。

分治法[编辑]

利用分治法将棋盘分成很多小块,计算出每一小块中的所有可能路径,然后将这些小块合并再计算所有可能的路径。

人工神经网络方法[编辑]

骑士巡逻问题同样可以使用人工神经网络来解决。[13]

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. ^ Enumerating the Knight's Tour. 
  13. ^ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.

外部連結[编辑]