关于骑士巡逻 | 瓦恩斯多夫规则、开放与封闭巡逻

印度诗人楼陀罗吒（Rudrata）在 9 世纪写成的《诗庄严论》（Kavyalankara）中，有一节诗被排在半个棋盘上，可以沿着马的路径读出来。莱昂哈德·欧拉在 1759 年写出了第一篇关于骑士巡逻的数学研究，给出了构造巡逻以及把巡逻变成封闭巡逻的方法。

把每个格子看作一个点，把马的每一步看作连接两个点的一条线。这样，骑士巡逻就是一条恰好经过每个点一次的路径，数学家称之为哈密顿路径；封闭巡逻则是哈密顿回路。对大多数网络来说，这样的路径很难找到。马的网络却很慷慨：它的巡逻路线非常多，一条好的规则很快就能找到一条。

H. C. 冯·瓦恩斯多夫在 1823 年描述了他的规则：总是跳到后续走法最少的格子。边缘上的格子邻居很少，所以这条规则会早早走到它们，而不是把它们孤零零地留在后面。两个格子打平时就需要做出选择，运气不好的选择仍可能让马卡住。在应用中，金色数字标出了这条规则会选择的格子。

“求解”按照瓦恩斯多夫的顺序走，但并不盲目相信它。它进行深度优先搜索，一旦某个未走过的格子再也到不了，就放弃这一分支，尝试下一步。在不超过 10×10 的棋盘上，它通常马上就能找到一条巡逻路线。如果你自己的路径已把马困住，它会先退回几步。

马每走一步，所在格子的颜色都会改变。在 5×5 这样边长为奇数的棋盘上，与角格同色的格子比另一种颜色多一个，所以巡逻必须在角格的颜色上开始和结束。在这种棋盘上封闭巡逻是不可能的，因为颜色交替的回路中两种颜色的格子一样多。在边长为偶数的棋盘上，从 6×6 起就有封闭巡逻。

打开骑士巡逻，点击一个格子开始。高亮的格子是合法的跳法，金色数字是瓦恩斯多夫的选择，棋盘会记下你走的顺序。“大小”把棋盘设为 5×5 到 10×10，“封闭巡逻”让“求解”找一条回路，“撤销”可以收回任何一步。把完成的路径保存为 PNG。

常见问题

谁最早研究骑士巡逻？

早在有人从数学上研究之前，人们就已经知道巡逻路线。莱昂哈德·欧拉在 1759 年写出了第一篇数学论述，瓦恩斯多夫在 1823 年提出了他的规则。

每种棋盘上都有巡逻吗？

从 5×5 起的正方形棋盘都有开放巡逻，其中从 6×6 起边长为偶数的棋盘也有封闭巡逻。2×2、3×3 和 4×4 的棋盘根本没有巡逻。

一个国际象棋棋盘上有多少种巡逻？

如果把一条巡逻和反向走的同一条巡逻分开计算，共有 26,534,728,821,064 种封闭巡逻。开放巡逻的数量约为 1.96 亿亿。

PictorX 会上传什么吗？

不会。棋盘画在你浏览器里的画布上。“保存”会下载 PNG，“编辑”会在 PictorX 编辑器中打开那张图。

在浏览器中打开 PictorX — 无需安装，无需信用卡即可启动。