华容道之最（一）一点历史和由来

小时候在商店里见过华容道玩具，和陆战棋、象棋这些放在一块儿卖的。塑料做的十个棋子上印着曹操和关张赵马黄还有四个小兵的图像。现在回想起来做工是很粗糙的，但在当时小孩们的眼里，仍然是不可多得的一件宝贝。不记得最终是不是拥有过一套，但印象最深的还是隔着玻璃橱窗看到的曹操们。

后来大学的时候学了一点编程，又玩了点三国志游戏，就想着自己做一个华容道试试，还真的成功了。程序是用Visual Basic写的，具体的时间想不起来了，好在当时有给程序做“关于”窗口的习惯，也就是版权页，“华容道3.0，for Windows98，1999.5”，快十年了呵。至于为什么是3.0，回想起来，大约是之前在试验求解算法的时候界面做得很丑，后来算法搞定了就在这上面用了点心思，把三国志五上的图片扒下来做棋子，这中间升级了两次。当时用的机器是赛扬300A的，我的程序求“横刀立马”的最少步数要一分钟，已然很激动和得意了。前几天我把这个程序翻了出来，把不兼容的地方稍微改了改，还能跑，后面文章里的图都是用这个程序生成的。

然后光阴似箭日月如梭，前一阵子不知道为什么又想起华容道了。这时候想的已经不是某个布局最少要多少步走出来，而是华容道最复杂能复杂到什么程度？也就是说一共有多少种可能的布局？最难的一个布局要多少步？很快搜索引擎就把我带到了半瓶墨水的Blog，原来不久前他已经解决了这个问题。从他那里我又逛到黄志华先生的Blog。黄先生对华容道的研究就完全不是我这样的“业余爱好者”可以比拟的了。我很赞同他说的华容道的求解目标不应该局限于“曹操逃出”这一结局，镜影、倒影、反影这些玩法往往更有挑战性。再者，华容道的棋子都是有名字的，比如马超和黄忠，在横刀立马里都是竖向1x2的棋子，如果我们在求镜像的时候要求这些棋子也要一一对应地转过来，就又引出了严格镜影、严格倒影和严格反影这些更难上一层的玩法。再推想开去，我上面那个问题又浮现出来了，从任意一个布局移动到另一个布局(包括镜影等)的最少步数，最大能大到多少呢？

如果从图论的角度来看，一个个布局就相当于节点，这些节点组成了若干个连通无权无向图，最长的最短路径，也就是图的“直径”，求解这一问题应该是很有意思的。我没有办法在数学的角度上解这道题，还是得借助计算机的穷尽搜索。埋头编了几个程序以后，这些答案终于一一浮出水面了。于是我想把它们记录下来，如果后来人有缘看到，也可以做一个参照比对。