騎士巡禮（）是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格，而且每个网格只能夠经过一次。假若騎士能夠從走回到最初位置，則稱此巡禮為「封閉式巡禮」，否則，稱為「開放巡禮」。對於8*8棋盤，一共有26,534,728,821,064種封閉巡禮，有19,591,828,170,979,904種開放式巡禮。
由骑士巡禮引申出了一个著名的数学问题 ：骑士巡禮问题--找出所有的骑士巡禮路徑。編寫一個程式来找出骑士巡禮路徑經常在计算机系的学生的练习中出现。骑士巡禮问题的变种包括各种尺寸的棋盘甚至非正方形的棋盘。
历史
执行的骑士巡逻。由于其路线是一条闭路，因此从棋盘上任何一点开始都能完成巡逻。]]
已知的最早的骑士巡逻问题可以追溯到九世紀的古印度恰圖蘭卡。
欧拉是最早研究骑士巡逻的数学家中的一员，而H·C·馮·汪斯道夫（H. C. von Warnsdorff）在1823年提出了第一个系统化解决骑士巡逻问题的方法——汪斯道夫规则。
在20世纪，一批乌力波的作家将这个问题用在了其它的地方。最明显的例子：乔治·佩雷克的小说《》的章节顺序就是按照棋盘的骑士巡逻路径来编排的。在2010年国际象棋世界冠军对抗赛的第六场比赛中，棋手维斯瓦纳坦·阿南德连续13次移动骑士（使用了两个骑士），在线评论员打趣地说阿南德试图在游戏过程中解决骑士巡逻问题。
实质
骑士巡逻问题实际上是哈密顿路径问题的一种特殊形式，寻找骑士巡逻的闭巡逻路径的个数实际上也是哈密顿循环问题的一种特殊形式。但是和一般的哈密顿路径问题不同，骑士巡逻问题可以在线性时间内解决。
路径的个数
*在一个的棋盘中，有26,534,728,821,064中有向封闭巡逻路径（相互对称的巡逻路径被视为不同的巡逻路径）。
棋盘中开巡逻的个数为19,591,828,170,979,904。对于n\times n（n*=1，2……）的棋盘中开巡逻的个数是：
: 1, 0, 0, 0, 1728, 6637920, 165575218320,19591828170979904,……（）
*Schwenk证明了，除了以下3種情況外，任何的（m\len）棋盘都至少有1个闭巡逻，。
#m和n都为奇数
#m= 1, 2, 4
#m= 3且n= 4, 6, 8
*Cull和Conrad证明了对于任何一个（5\lem\len）棋盘，至少有一个（可能是开巡逻）骑士巡逻路径。如此大的运算量已经超出了现代计算机的运算能力。
分治法
利用分治法将棋盘分成很多小块，计算出每一小块中的所有可能路径，然后将这些小块合并再计算所有可能的路径。
人工神经网络方法
骑士巡逻问题同样可以使用人工神经网络来解决。
汪斯道夫規律
汪斯道夫規律指在所有可走且未經過的方格中，騎士只可能走這個方格：從該格出发，騎士能跳的方格數最少；如果可跳的方格數相等，則從當前位置看，方格序号小的優先。依照這一規律往往可以找到一條路徑但並不一定能夠成功。
參考資料
外部連結
- [http://www.ktn.freeuk.com/ Knight's Tour Notes]
- https://web.archive.org/web/20051219005826/http://www.borderschess.org/KnightTour.htm Knight's Tour
- [http://episte.math.ntu.edu.tw/java/jav_knight/ JAVA：Knight's tour]
评论 (0)