Mathematica 谜中智 | 趣味象棋 一马平川【谜底篇】

中国象棋是中华民族的文化瑰宝，您找到答案了吗？

谢谢@笙箫默同学积极的参与并分享了他的答案：

代码：http://o8aucf9ny.bkt.clouddn.com/chessCode.png

结果：http://o8aucf9ny.bkt.clouddn.com/chessLnew.gif

谜底

答案：

正确答案不唯一，且可行解肯定大于等于46种。

方法一：

采用回溯算法 + Warnsdorf 规则的方法，可获得1种答案。当马的初始坐标位置从 {8,1} 开始（即 x=8，y=1；或者说第8列第1行时），完成在棋盘上的全部巡回，马的落子位置坐标如下，详细步骤可参见解题和演示。

方法二：

采用 FindHamiltonPath 函数的 Hamilton Laceable Knight 算法，在固定一种初始位置条件下，可获得45种答案。取决于马的终止位置，详细步骤可参见解题。

总结：

由于组合问题的庞大，正确答案不唯一，且可行解肯定大于等于46种。根据两种方法比较，在边界条件（初始位置和终止位置）完全一样的前提下，两种算法获得了两个不同的解。所以，本文作者猜想正确解的数量很可能会是90种，甚至大于90种。

解题

使用函数：Module, While, Which, Select, KnightTourGraph, FindHamiltonPath

在谜面部分我们谈了关于“抄袭问题”的第一个层次，不要抄袭无价值的作品。如下我们接着谈“抄袭”的第二个层次，对高价值的作品要有智慧的“抄袭”和再次创新。

在此先引用乔帮主（乔布斯）的话：“我们从不以偷窃别人的伟大作品为耻！”（原句：We have always been shameless about stealing great ideas.），其实乔帮主这句话本身就是源于著名艺术家毕加索的名言：“好的艺术家拷贝，伟大的艺术家剽窃。”（原句：Good artist copy, great artists steal.）无论乔布斯还是毕加索这句话，都是在告诉世人，普通的艺术家善于临摹和模仿，但其作品只能达到形似，却缺乏灵魂和突破；伟大的艺术家不耻于复制和剽窃，他们不是盲目地拾人牙慧，而是继承前人和竞争对手的思想和精髓，并且能青出于蓝而胜于蓝，最后设计出更佳的作品或自成体系成为领域的领军人物。早期的图形操作系统，苹果 Mac 和微软 Windows 其实都是从施乐 Xerox “搬过来”的。乔帮主对抄袭的态度：坦白承认，面对审判，收获利益，承担责任。至少比盖茨先生的说法要光明磊落的多，比尔·盖茨曾言：“我不过是在将别人丢弃在垃圾桶里的代码捡回来。”同时，不可否认乔布斯和盖茨大多数时候的抄袭不是简单抄袭，而是在抄创新、改创新，把抄来的元素，改造的比原来更好。

所以“对高价值的作品”我们要有一个明确的判断、态度和立场，还是乔帮主说得好"伟大作品”（呵呵）。此外，还要有一套清晰的实施策略，如何进行“有智慧的抄袭”或者说“再次创新”。综上所述，根据作品的价值和伟大程度，通常直接影响了人们对之抄袭与否的态度。

好了，究竟是抄袭还是创新，我们就聊到这里了，让我们回到本道谜题的答案部分。骑士巡回游（Knights Tour）是计算机科学领域的一道经典算法题。本题同国际象棋中骑士巡回游的唯一区别在于边界条件，国际象棋的棋盘尺寸为 8*8，而中国象棋的棋盘尺寸为10*9。

方法一：回溯算法+启发式规则（Backtracking + Warnsdorf）

回溯算法或者说深度优先搜索，是一种常用基本的搜索算法。简单地说，就是一条道走到黑；遇到死胡同，碰壁回头，接着走；直到走出死胡同；如果走不出，那就死在胡同里。学术一点的说法，就是往深度方向搜索，试图打通树结构，如果在树中未搜到正确解，那就在跳回到上个节点，找下个分支。这种方法有一定优势，对某些层多的树可能效果好，但回溯算法也有缺点，就是对有些问题求解通常很慢。

于是， H. C.von Warnsdorf 在1823年写了一篇名为 Des Rösselsprungs einfachste undallgemeinste Lösung 的文章，参考文献[3]，可能是关于求解骑士巡回游问题算法最早的论文了。这篇文章中他记载了一种启发式算法并建议，结合棋子已完成的步数，并根据棋子当前位置，对下一个可落子位置进行评分或权重，评分多少又根据该位置的下一步是可落子位置数是多少而定。正因为这种权重，使得深度搜索变得有一种特定的导向，因而大大提高了算法的效率。这类基于个人经验的方法统称为启发式算法，Warnsdorf 方法的实质就是一种有权重和经验导向的算法，它会倾向于把棋子当前周边的空位先走完，并不留孤位。对于棋盘尺寸较小的情况下被证明是有效的，如 8*8 的国际象棋和 10*9 中国象棋，参考文献[1]和[2]。

如下我们着重讲述回溯 + Warnsdorf 启发式规则算法的实现。马可以在棋盘上向前后左右，4个方向，共8个位置，进行跳跃。在坐标下，定量描述，马移动一步的的数值，通过对棋子在棋盘坐标点 X 和 Y 的增量来表示。换言之，马走日，将它定量的表示出来。老实说，我真心很膜拜第一个写出这行代码的人，可能是早期电子游戏的开发者。人类玩了几百年的棋类游戏，就被他通过坐标系加上数值定量描述，变得如此的科学，真是了不起的一步，随后就开启了一个人工智能和科学下棋的新时代。

接着，定义一个函数 boundaryCheck，它的作用就是检查在每一步选择新落子的位置时，是否满足边界条件。这里的边界包含两种概念，空间边界和时间边界，这两种边界必须同时都满足才接受。空间边界：定义棋子移动，允许落子在棋盘范围内接受的边界。因为中国象棋的棋盘尺寸为 10*9，也就是9列10行。故此，x 的值域范围为 [1, 9]，y 的值域范围为 [1, 10]。时间边界：定义一个棋盘计数表 boardHistory，它的作用实际是记录算法过程中，棋子“马”在棋盘上落子的顺序和位置，未落子的空区域设定未0，此处也一并检查，是否新落子位置为空位，排除重复落子的情况。后续算法中，我们还会详细讨论它的使用。

至此，我们来简单地评估一下中国骑士“马”巡回问题的计算复杂度，即最坏情况下的计算量。棋子每走一步有8种可能，即计算机中树的宽度；在棋盘上完成巡回，即在棋盘 10*9 的范围内应包含所有的落子，即树的深度。初步评估计算如下，可见这一组合问题的计算节点数又是个天文数字。

接着应用之前的条件，评估当前棋子下一步可落子的情况 Accessibility，实质就是从8种理论上可行的情况中检查落子是否在棋盘边界内。如果新的落子的位置在棋盘范围内，则接受并计数器加一；如果新落子的位置在边界外，则排除这种情况，计数器不变。这样就得到当前棋子的可行解的数量。

下一步就是 Warnsdorf 启发式规则描述，它是一种经验性的方法。根据当前落子位置，查看下一步可落子位置进行评分或权重，评分多少又根据该位置的下一步是可落子位置数是多少而定。

为了便于理解我们举个例子，如下图所示。当前马在 {8, 1} 上，那么下一步落子共3个选择，如蓝圈所示，分别在 {9, 3}、{6, 2} 和 {7, 3}。再进一步，如果落子位置为 {9, 3} 时，还可以有3个选择；如果落子位置为 {6, 2} 时，还可以有5个选择；如果落子位置为 {7, 3} 时，还可以有7个选择。

下面我们再改写一下函数，通过排序把落子位置少的列在前面，然后优先选取落子步数少的位置。或者说 Warnsdorf 规则通过先“偷看”了下一步棋，然后判断当前的抉择，把下一步落子位置数少的先走掉，尤其是仅剩一个空位的选项，这样就避免了后期在棋盘上出现“孤独空位”的尴尬。并且由于整个骑士图的特性，它会倾向于把邻近和外围四边的先走掉，然后再逐步进入中央区域。

前面都是些基本规则和边界的设定和准备工作，相对也比较简单，此处则是回溯算法。定义并记录棋盘落子状态boardHistory变量，并将落子状态用数字记录为三类，0代表空位，1代表马的初始位置，2-90数字则代表随后的落子先后顺序，用变量 moveNumber 记录。调用一下Steps 函数，就获得了马的巡回游问题的解了。

演示一下，在 n*m 的棋盘上计算骑士巡回问题的回溯 + Warnsdorf 规则算法。算法详细的解释已在之前解题过程中进行了诠释，此次不再重复展开。（下载链接：http://demonstrations.wolfram.com/AChineseKnightsTour/）

之前已经详细讲述说如何通过 Mathematica 图形和图形的功能，获得一张中国象棋马的图像了。

将以上棋子插入到二维棋盘上，仅显示棋子的当前位置，并通过虚线描述棋子历史的移动步数或轨迹。

绘制一张中国象棋的棋盘，并通过 Epilog 函数留有接口，以供动图的更新棋子在棋盘上的位置和轨迹。

演示和操控函数，定义骑士巡回问题的初始变量，包括棋子的初始位置和当前巡回的步数，以及设定棋盘大小边界。

之前我们花了较多的笔墨介绍了回溯算法 + 启发式规则，这种算法在小棋盘内是有效的。此外主要目的是为了帮助各位学习和掌握基本的算法设计。但是启发式算法也有缺点，就是它通常是由个人的实践经验中提炼形成，并未被数学上严格地证明过，为什么一定要这样计算说不清楚。如本算法中，为什么一定要采用可落子位置权重作为判断条件。其实这个问题不知道，也未被有效证明，反正这样做能在一定范围内有效。回溯启发式规则对于大尺寸棋盘（如10*10以上）未必或不能找出正确解，所以这种算法求解的通用性存在问题。

写到这里我也要坦白一下，其实我也是“抄来的”。百年以来，骑士问题的启发式算法大家都是抄 H.Warnsdorf 的，参考文献[4-5]。Mathematica 的源代码，我是抄 J. Warendorff，参考文献[2]。但是抄，要抄思想，要抄了能懂，能自己理解，能理解才是正真的拥有。抄了不懂，那还不是白抄了，又何必去抄呢？

方法二：哈密顿可分解骑士算法（Hamilton-laceableKnight）

在数学图论中，骑士巡回问题可以归结为是一种哈密顿路径的特殊情况。尽管哈密顿路径问题是一个 NP 完全问题（NP-Complete Problem）但在许多图和实践中，通过启发式算法可以在线性时间内下找到可行解。

我们结合 Dupuis 和 Wagon 的最新研究成果，他们提出了哈密顿可分解骑士算法（Hamilton-laceableKnight），感兴趣的读者可参考文献[6]和[7]。其实它已经被集成到 Mathematica 最新版中去了，KnightTourGraph 和 FindHamiltonPath 函数。如下我们结合中国骑士巡回游问题，来讲解一下这两函数的用法。

先用 KnightTourGraph 生成中国象棋（棋盘尺寸为 10*9）的骑士图，并附上顶点标号。骑士图看上去有点像弹簧床。总之，四周区域的顶点连线少，中间区域的连线多。

为了看得再清晰一些，我们把象棋棋盘和骑士图，合并在一起。此处的关键是看懂和理解骑士图，也就是马的落子位的全部关联图。

调用一下FindHamiltonPath 函数，设置初始顶点为编号71，坐标 {8, 1}，终止顶点为编号76，坐标 {8, 6}。一行代码，蹦答案。

可视化一下，把骑士巡回路径通过红色高亮显示在棋盘上。

如果初始位置已知，编号为71，坐标为 {8, 1}，那么根据终止位置在棋盘上不同的位置，把所以的解都找出来，总共45个可选解。

FindHamiltonPath 函数的算法也是一种启发式算法，但相对于之前回溯算法的优势也显而易见，它不仅可以控制初始位置，而且可以控制终止位置。最后放大招 Manipulate，把45个可行解和巡回路径都动态演示出来，解题完毕。

这里先提一个问题：为什么您需要选用 Mathematica 作为科学计算的工具？

其实本题算法 KnightTourGraph 和 FindHamiltonPath 函数就是英国教授 S. Wagon 和Wolfram 公司一起合作开发的。Wolfram 公司汇聚了全球最顶级的数学家、计算机专家和一流的算法程序工程师，他们小心翼翼地将最新的数学和计算成果以及相关概念和知识梳理干净，开发和集成到 Mathematica 中去，并且编写和翻译了上百万字的用户使用手册（含中文），它基本就是一部现代数学和计算应用的百科全书。当你在使用 Mathematica 时，绝对不会觉得是孤军奋战在解决难题。相反地，因为有了 Mathematica，在你的背后有成千上万的科学家和数学家作为你的强大后盾，你可以随时随地的调用最先进、最前沿的的算法和成果，作为您的解题工具。

故事还没有全部讲完，当然作为中国或世界的骑士巡回问题还没彻底和完全解决，因为哈密顿路径问题是一个 NP 完全问题。搞计算机和算法的同仁懂得，P=NP？问题是百万美元奖金的千禧年世界数学难题之一。 NP 完全问题解不出来不丢人，因为大家都解不出来。从一道小谜题，牵扯出这么一个大难题，也在我的意料之外。

或许有一天，您提出的算法和方法能够被集成在 Mathematica 中，那就是对世界数学和计算界莫大的贡献和个人荣耀了。

最后，关于 Mathematica 象棋编程可参见演示项目[9]；关于象棋和人工智能参考文献[10]是一部经典之作，并有中译本值得一读。

参考文献：

[1] F. Wu,"A Chinese Knights Tour", Wolfram DemonstrationsProject. （http://www.demonstrations.wolfram.com/AChineseKnightsTour/）

[2] J. Warendorff, "The Knights Tour",Wolfram Demonstrations Project.（http://demonstrations.wolfram.com/TheKnightsTour/）

[3] H. C. von Warnsdorff, "DesRösselsprungs Einfachste und Allgemeinste Lösung", Schmalkalden, 1823.

[4] I. Pohl, "A Method for Finding Hamilton Paths and Knight'sTours", Communications of the ACM, Vol.10 (7), 1967, pp. 446 - 449.

[5] K. Alwan, K. Waters, "Finding Re-entrant Knight's Tours on N-by-MBoards", ACM Annual Southeast Conference, 1992, pp. 377 - 382.

[6] M. Dupuis, S. Wagon, "Laceable Knights", ARS Math. Contemp., 2015, pp.115-124.

[7] S. Wagon, "Laceable Knight Graphs", Wolfram DemonstrationsProject.（http://demonstrations.wolfram.com/LaceableKnightGraphs/）

[8] J. McLoone, "Solving the Knight's Tour on and off theChess-board", Wolfram Blog.（http://blog.wolfram.com/2014/09/04/solving-the-knights-tour-on-and-off-the-chess-board/）

[9] K. Scherer, "Chess", Wolfram Demonstrations Project.（http://demonstrations.wolfram.com/Chess/）

[10] F. H. Hsu, Behind Deep Blue: Building the Computer that Defeated theWorld Chess Champion, Princeton University Press. 2002

许峰雄著，黄军英等译，追寻人工智能圣杯之旅：深蓝揭秘 ，上海科技教育出版社，2005