偶看新闻度寒小说集:华容道解法
来源：百度文库 编辑：偶看新闻 时间：2024/06/03 03:16:56
华容道游戏的解法
最早系统研究游戏华容道的是苏州大学数学教授许莼舫先生。1952年，他在《数学漫谈》中对这个游戏作了详细的分析，总结出8条规则。这8条可以归纳为以下4点：
1，四个小兵必须两两在一起，不要分开；
2，曹操，关羽，大将移动时前面应有两个小兵开路；
3，曹操移动时后面还应有两个小兵追赶；
4，以下三种状况，其中各块都可局部（不妨碍其他地方）任意移动。
在此基础上，许莼舫提出了100步解法。后来，美国一个律师托马斯.莱曼(Thomas B.Lenann)发现一个新的解法，由加德纳公布在1964年3月《科学美国人》上，有81步，称加德纳解法。
游戏华容道有不同的开局，根据5个矩形块的放法分类，除了5个都竖放是步可能的以外，有一横式，二横式，三横式，四横式，五横式。下面举几个例子。
研究华容道游戏，除了其历史外，至少有以下几个问题：
1，有多少种开局；
2，判断有解；
3，给出最优解；
4，计算机求解。
因此，华容道是个数学游戏。
国内国外都有一些华容道的爱好者研究者。姜长英先生1985年发起组织“华容道研究会”，他们有了不少结果。特别是原北京工业学院副院长齐尧的网络研究，可以说完全解决了华容道游戏方法。他研究了一横式华容道的各种关键状态共54图，找出其间关系，画出关系图。于是任何一横式华容道都可以经少数几步到达某一个关键状态，其解法也就给出了。对 二横式，三横式，四横式，他也都画出了关系图。
用计算机解决华容道游戏，http://www.math.sdu.edu.cn/html/sxjm/examples/ex5.htm上有这样的说法：“笔者编制的软件HRDE的贡献是成功地实现了一种系统搜索（Systematic searching）算法，它能在较短时间内，对用户摆放的任何一种布局判断是否有解。如果有解，则解出它的最少步法。然后，它会在屏幕上用动画方式移动棋子以显示它的运算方法。也可以用一连串的图形来静止地显示每一步的走法，便于用户仔细地观察研究。一般情况下，在已经很普及的IBM486计算机上解一道题仅需要一两分钟，在较慢的286计算机上则大约需要十几分钟。根据它的算法的原理可以肯定，它推导出的结果是绝对可信的。也就是说，它所解出的走法一定是该布局的最少步法。 ”
华容道游戏又有很多发展，在国内外产生了很多类似的游戏。如推箱子游戏。
推箱子游戏出现在计算机中最早起源于1994年台湾省李果兆开发的仓库世家，又名仓库番，箱子只可以推, 不可以拉, 而且一次只能推动一个， 胜利条件就是把所有的箱子都推到目的地 。现在网上有很多种推箱子游戏。