骑士巡礼（英语：Knight's tour）是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格，而且每个网格只能够经过一次。假若骑士能够从走回到最初位置，则称此巡礼为“封闭式巡礼”，否则，称为“开放巡礼”。对于8*8棋盘，一共有26,534,728,821,064种封闭巡礼，有19,591,828,170,979,904种开放式巡礼。[1][2][3]
由骑士巡礼引申出了一个著名的数学问题 ：骑士巡礼问题--找出所有的骑士巡礼路径。编写一个程序来找出骑士巡礼路径经常在计算机系的学生的练习中出现。骑士巡礼问题的变种包括各种尺寸的棋盘甚至非正方形的棋盘。
历史
已知的最早的骑士巡逻问题可以追溯到九世纪的古印度恰图兰卡。[5]
欧拉是最早研究骑士巡逻的数学家中的一员，而H·C·冯·汪斯道夫（H. C. von Warnsdorff）在1823年提出了第一个系统化解决骑士巡逻问题的方法——汪斯道夫规则。
在20世纪，一批乌力波的作家将这个问题用在了其它的地方。最明显的例子：乔治·佩雷克的小说《人生使用法》的章节顺序就是按照10×10棋盘的骑士巡逻路径来编排的。在2010年国际象棋世界冠军对抗赛的第六场比赛中，棋手维斯瓦纳坦·阿南德连续13次移动骑士（使用了两个骑士），在线评论员打趣地说阿南德试图在游戏过程中解决骑士巡逻问题。
实质
骑士巡逻问题实际上是哈密顿路径问题的一种特殊形式，寻找骑士巡逻的闭巡逻路径的个数实际上也是哈密顿循环问题的一种特殊形式。但是和一般的哈密顿路径问题不同，骑士巡逻问题可以在线性时间内解决。[6]
路径的个数
- 在一个8×8的棋盘中，有26,534,728,821,064中有向封闭巡逻路径（相互对称的巡逻路径被视为不同的巡逻路径）。[7][3]
- 在6×6的棋盘中，共有9862个闭巡逻。[8]
- 8×8棋盘中开巡逻的个数为19,591,828,170,979,904。对于（n=1，2……）的棋盘中开巡逻的个数是：
- 1, 0, 0, 0, 1728, 6637920, 165575218320,19591828170979904,……（
A165134）
- Schwenk证明了，除了以下3种情况外，任何的m×n（mn）棋盘都至少有1个闭巡逻，。[9]
- m和n都为奇数
- m= 1, 2, 4
- m= 3且n= 4, 6, 8
解决方法
用穷举法来寻找骑士巡逻路径适用于格数较小的棋盘，因为当方格数过多时，可能的路径过多。例如，8×8棋盘中大约有4×10^51种可能的路径。[11]如此大的运算量已经超出了现代计算机的运算能力。
利用分治法将棋盘分成很多小块，计算出每一小块中的所有可能路径，然后将这些小块合并再计算所有可能的路径。
汪斯道夫规律指在所有可走且未经过的方格中，骑士只可能走这个方格：从该格出发，骑士能跳的方格数最少；如果可跳的方格数相等，则从当前位置看，方格序号小的优先。依照这一规律往往可以找到一条路径但并不一定能够成功。
参考资料
外部链接
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
