历史

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

已知的最早的骑士巡逻问题可以追溯到九世纪的古印度恰图兰卡。

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

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

实质

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

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

路径的个数

在一个8×8的棋盘中，有26,534,728,821,064中有向封闭巡逻路径（相互对称的巡逻路径被视为不同的巡逻路径）。 。

在6×6的棋盘中，共有9862个闭巡逻。

8×8棋盘中开巡逻的个数仍然未知。对于 n × × --> n {\displaystyle n\times n} （n=1，2……）的棋盘中开巡逻的个数是：

Schwenk证明了对于任何一个m×n（m ≤ ≤ --> {\displaystyle \leq } n）棋盘都有1或1个以上的闭巡逻，除非满足以下3中情况中的一种或更多。

m和n都为奇数

m= 1, 2, 4

m= 3且n= 4, 6, 8

Cull和Conrad证明了对于任何一个m×n（m ≤ ≤ --> {\displaystyle \leq } n且m ≥ ≥ --> {\displaystyle \geq } 5）棋盘，至少有一个（可能是开巡逻）骑士巡逻路径。

解决方法

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

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

穷举法

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

分治法

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

人工神经网络方法

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

Warnsdorff规则

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

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。