闯过华容道

华容道游戏很难用数字方法求解。作者所编计算机程序HRDE可以对任何布局解出答案。用它发现了文献上有不少答案实际上并非最少步法。

关于华容道游戏

"华容道"是世界著名的智力游戏。在国外和魔方、独粒钻石并列，被誉为"智力游戏界三大不可思议"并被编入学校的教科书。日本藤村幸三朗曾在《数理科学》杂志上发表华容道基本布局的最少步法为85步。后来清水达雄找出更少的步法为83步。美国著名数学家马丁·加德纳又进一步把它减少为81步。此后，至今还未曾见到打破这一记录的报道。1985～1986年在中国曾有《中国少年报》五种刊物先后举办过三次华容道游戏的有奖比赛，共列出"横刀立马"等八种布局（见图1），征求最少步法的答案。在竞赛前有人曾预言可能会创造出新的世界记录。虽然在1985年9月18日的《北京晚报》上有报道说在比赛中已有人打破了马丁·加德纳的 81步记录。但并未见到进一步的详细报道，可能实际上并不是同一种布局。因为在此之前也曾经出现过类似的情况。中央电视台在1985年第6期的《电视周报》上就曾登载过有人声称打破了马丁·加德纳的81步记录，但后来被确认是不同的布局。

华容道游戏的布局可见图1中的例子。棋盘有20个方格，上面有大小不等的10个棋子，共占去18个方格。只有两个空的方格作为活动的余地。所有棋子只能利用这两个空格在棋盘的平面上平移而不得跳越其他的棋子，当然也不得越出边框。游戏的目标是要把最大的一个棋子（即A，占4格）移到最下部的中央出口处。为了用最少的步数达到目的，显然必须最合理地运筹所有的棋子。由于形状不同的棋子互相阻塞，使得本游戏具有相当大的难度。国际上公认这类问题很难用数学方法来解决。附图中的"横刀立马"就是马丁·加德纳等人所研究的基本布局。后来，又衍生出许许多多新的布局。图1中只是极少数几个例子。

计算机解题的效果

笔者编制的软件HRDE的贡献是成功地实现了一种系统搜索（Systematic searching）算法，它能在较短时间内，对用户摆放的任何一种布局判断是否有解。如果有解，则解出它的最少步法。然后，它会在屏幕上用动画方式移动棋子以显示它的运算方法。也可以用一连串的图形来静止地显示每一步的走法，便于用户仔细地观察研究。一般情况下，在已经很普及的IBM486计算机上解一道题仅需要一两分钟，在较慢的286计算机上则大约需要十几分钟。根据它的算法的原理可以肯定，它推导出的结果是绝对可信的。也就是说，它所解出的走法一定是该布局的最少步法。

作为一种检验，用本软件对文献上发表过的若干布局进行了验证，得到了一些有趣的结果。

首先，软件HRDE确认了马丁·加德纳的81步记录是最少步法。想要打破这一记录是不可能的。但是它也发现了文献上发表的另外一些布局的答案实际上并非最少步法。

例如，1986年牛津大学出版的《SLIDING PIECE PUZZLES》一书中列出了在国外曾经出售过的12种华容道游戏（书中编号为C15，C23－26，C27a～d，C30，C41，C42a）并给出了最少步法的答案。经过HRDE的验算，其中11个答案的确是最少步法，但编号为C30名Top Secret的一种布局（见图 1）书中给的 67步走法并不是最少步数。最少步法应是63步。比较这两种走法可以看出差别是在第20至35步（见图2）。书中走15步而HRDE只用11步就达到了相同的结果（有一点差别，但不影响后面的走法）。

又如，1987年出版的《独立钻石和华容道》一书中除横刀立马以外，还列出26种不同的华容道布局，其中19种有答案经过HPDE的验算，9种布局的答案确是最少步数。但另外10个答案不是最少步数。部分检验结果列在表1。

这些布局的新的走法请见本文末。

表1包含了上述竞赛的题目。《动手做》的竞赛题是：横刀、守口之一、层层之二、四路进兵。《文化娱乐》的题目是：横刀、守口之二、层层之二、水泄不通。《中国少年报》、《父母必读》和《少年科学画报》的题目是：横刀、插翅难飞、层层之一。

一个布局可能的走法越多，计算机解它所用的时间也越多。因此表中列出的运算时间反映了解答该布局的难度。可以看到，横刀立马并不是最难的，五虎拦路则相对较易。国外对每种布局的难易也有所评估，但笔者以为计算机的反映也许更有根据些。

此书中还有七种布局没有答案。现将HRDE得到的最少步数列于表2。

HRDE程序的算法原理

HRDE采用的算法原理很简单，也很直观。简言之，就是利用计算机快速处理大量数据的能力。让它把每个布局的所有可能的走法毫无遗漏地罗列出来，然后从中找出步数最少的走法。因此，只要保证不遗漏掉任何走法，运算的结果就是可靠的。具体到每一步，可能存在的走法并不多，保证这一点并不难。

编写此程序的要点是：（一）选择最佳的编码方法，既要用最少字节表达每个布局以节省内存，又要利于解析该布局的各种可能的走法，还要能够在数以万计的布局中迅速进行搜寻和对比。本程序表达每个布局只用4个字节；（二）解析每一步的走法时，保证不遗漏掉任何可能存在的走法；（三）必须设法避免一切重复的和镜像相同的走法，否则数据量之大会难以应付；（四）为了最后追溯出某种走法的全过程，采用了树状链式数据结构，每一布局都有指针指向上一步布局的地址。

笔者首次编成此程序是在1985年。当时是在CROMEM－COZ2D微机上用汇编语言实现的。由于64K内存不够用，运行中还必须把数据放到软盘上。解一道题要长达 2～ 5小时之久。1994年才把此程序移植到IBM486微型机上，增加了彩色动画显示。解题时间大大缩短到三分钟左右，达到了可实用的速度。

HRDE在解题时，每推进一步就把这一步可能有的走法的数目显示在屏幕上。实际运行的情况是，第一步一般只有2～8种走法。但每种走法之后又有若干种走法，因此从第二步起走法的数目不断增加。大约30步之后会达到极大值。此后略有减少。多数布局还会出现第二次极大值。个别布局（例如水泄不通）还出现第三次极大值。最大的极大值就是这一布局可能有的走法的数目。一般在200至800之间（10棋子），或1400左右（11棋子〕，或1800之间（12棋子）。这数目包括所有走得通和走不通的走法，但不包括一切重复的和镜像相同的走法。当然，这是计算机不加选择地罗列所有走法的结果。如果由人来选择，其中有些走法肯定不必考虑的。

如果某个布局的走法的数目达到极大值之后迅速降为零，软件就报告这一布局是走不通的。

可见，HRDE是研究华容道游戏的一种有力工具。用它来研究各种布局的走法也许能发现一些规律。在研究数学方法时，它至少能起到验证的作用。

HRDE也是游戏程序
本软件也是一个高雅的智力游戏。有助于增进逻辑思维能力。人们可以随意设计一种新布局。然后用按键移动棋子。每一步都将被计算机记录下来（省去了记录和涂改的麻烦），每步的图形会依次排列在屏幕上（每屏显示24步，然后滚动），可以一览无遗。此外还提供了以下功能：

1）随时可以退回去任意步数再重走；
2）如果重复了以前已经走过的图形，或镜像与之相同的图形，软件会提示用户，用不着自己去逐个查找；
3）随时可以把用户的走法存入磁盘，便于以后继续研究；
4）随时可用动画方式显示走法；
5）可以和计算机的答案比较，看是否是最少步数；
6）无论哪一步都可以要求计算机帮助，计算机会指出当前情况下的最佳走法。
显然， HRDE也可以方便地用于华容道游戏的竞赛。当然，竞赛中必须禁止使用计算机解题的功能。
软件运行中有菜单及命令提示，不必事先学习就能使用。HRDE全部用汇编语言编写，因此占内存少、运行速度快。即便如此，由于处理的数据量较大，计算机至少要提供256k内存供本软件使用。

限制应用此软件的条件是：最大棋子只允许一个：最小棋子允许有4～8个（棋子总数相应为10～12个），其余棋子任选；棋盘上只许有两个空格。不满足这些条件软件将拒绝运行。

另一个限制是，游戏的目标必须是把棋子A移动到出口处。国外文献上有一些游戏的目标是要把某些棋子移动到指定的新位置。HRDE目前还不能解决这类题目。但经过少量修改应该是可以实现的。

答案

国内外文献中已发表的某些华容道布局的答案实际上并不是最少步数。以下是运行 HRDE软件得到的最少步法。我们沿用L．E．Hordern的记录方法，即在多数情况下只要指明走哪一个棋子就够了，只有少数情况下才需要指明如何走。这时用以下符号来表示。L向左；R向右；U向上；D向下；！只走一格；＃必须拐弯（指最小棋子）。没有这些符号时，表示直走，到头为止（一格或两格）。棋子编号见图1。

（1） 横竖皆将（原文92步，现81步）
6 4 5 7 ＃ 9 6 8 3 5 7 9 L 2 A 7 5 1 7 L A 2 4 5 9 L 4 5 8＃3 1 9 L 4 5 8＃3 1 9 L 4 5＃ 2A 9 # 4 1 3 6 8 5 2 A 9 7 4 3 5 8 6 D 3 A 9 1 7 4 3 1 2 2 6R 5＃ 8＃ A 9 1 7 4 3 1 A 9 1 7 2 6 8 5 A 9 3 4 2 6 5 # A
（2）守口如瓶之一（原文 88步，现 81步）
5 7L 2 A 1 3 6 4 1 A 2 7＃ 9 8 4 1 6 ＃4 1 6 5 ＃7 9 5 6 ＃1 4 7 ＃ 9 5＃2 A 7 ＃9 4 1 8 6 D 5 2 A 7 3 9 1 5 6 7 1 4 D 1 A 7 1 3 9 1 4 2 8 R 5 ＃6＃A 7 1 3 9 1 4 A 8 3 2 8 6 5 A 7 1 9 2 8 5＃A
（3）守口如瓶之二（原文 10O步，现 99步）
7＃9 8 6 ＃3 1 A 2 4 7 R 2 A 1 3 6 ＃8 9 7＃4 A 5 6 ＃8 9 7 # 8 9 3 6＃ 51 6 U 5 1 A 4 81 2U 8 1 1 7 9 3 5 2＃8 7 ＃ 4 A 2＃8 5 3 9 1 7 4 A 2 6 8 3 7 1 9 5 D 3 9 2 1 6 8 3 5 4 9 R 1＃ 7＃ A 2 1 6 8 3 5 A 2 1 6 4 A 7 1 A 2 3 8 4 9 1＃A
（4）层层设防之二（原文122步，现120步）
9 L8＃4 2 A 1 3 5 2 4 8 9 6 7 2 5 3 1 L，A 4 5 2 7 6 9 8 2 7 6 # 7 8＃ 7 9 3 6 # 5 8 ＃4 A 6＃ 5 3 8 9 2 4 A 6 1 5 8＃ A 6 1 1 5 8 3 4 7 2U 9 7 2 A 6 1＃ 4 A 6 3 2 6＃ 7 9 A 1＃3 2 8 5 3 1 A 9 7 1# A 4 3 2 # A 1 6＃ 8 A 1 4 3 1＃ 4 3 9 7 8 6 D A 6 2 1 4 3 9 7 6 8 A 9 7 8 ＃A
（5）Top secret（原文67步，现 63步）
7 5 3 2 1 4 6 7 L A 1＃4 6 7 1 1 3 5 9 8 A 1 4 2 5 3＃ 4 7 R 6 2 4 1 A 8 9 3 D 5 1 4 2 7 U 6 U A 1 3 9 8 3 D 1 D A 7D 6D 2 5 4 9 8 3 1 A 9 8 1＃A
（6）三军联防（原文73步，现65步）
6 7 4 3 7＃ 3 4 2 1 A 7 5 8 4 6 9＃ 6 4 8 3 9 L 2 1 A 5＃ 3 8 9 U 4 6 2 1 A5 7
3 9＃ A 1 2 4 6 8 9 A 1 2 4 6 9＃ A 3 7 5 1 2 4 6 9 8 A 4 6 8＃A
（7）堵塞要道（原文 43步，现 40步）
5 9 6 7 4＃2 A 3 ＃7 5 6 9 8 4 2 D A 3 1 7 5 6 9 8 4 2 D A 1 3 D 7 5 6 9 8 4 2 A 9 8 2＃A
（8）水泄不通（原文80步，现79步）
9 7 6 8 9 U 7 6 5 4 8 9 U 5 4 9 A 1 3＃ 8 A 1 2 9 1＃ 4 5 A 3＃ 21＃ 4 5 6 7 A 5 4 1＃ 2 3 ＃5 4 2 1 9 D 3 8 5 4 A 7 6 1＃ 9 3 8＃5 4 A 1 9 6 7 1 9 D A 4 5 2 8 3 U 6 7 9 1 A 6 7 1＃A
（9）四路进兵（原文 67步，11 66步）
A 4 3 ＃2 A 4 3 ＃1 5 2 ＃7 6 A 3 ＃1 2 ＃7 6 9 8 A 6 7 2 0＃1 3 ＃6 7 1 2 5 D 3 4 6 7 A 8 9 2＃ 5 3 4＃ 6 7 A 2 5 9 8 2 5 D A 7 6 1 4 3 U 9 8 5 2 A 9 8 2＃ A

回首页