华容道

华容道游戏与重排九宫和重排十五类似，属于滑块类游戏。标准华容道是4×5的长方形棋盘，共有10枚棋子。其中，最大的一块是2×2，代表曹操；2×1的有5块，4块竖排的分别代表张飞、赵云、黄忠和马超，一块横排的代表关羽；还有4块1×1的代表卒。此外，盘面还空出2个单位面积，作为游戏时的滑动之路。游戏要求滑动棋子，使曹操移动到下端正中间的开口处逃脱（如图1-12所示）。这个故事来源于中国古代的文学名著《三国演义》。

图1-12所示的是典型的“横刀立马”开局，研究其解法的最小步数长期是热点问题。1964年，美国马丁·加德纳在《科学美国人》上公布了81步的解法。后来经过计算机的验证，确认这是最少步数解。

为了介绍这个最少步数解，我们采用“横刀立马”开局式，然后以10个数字代表10个滑块（如图1-13所示）。

解法如下，加下划线的表示只走半程（这里要解释一下“半程”的意思，如棋子9，它的右面有两个空格，“全程”是指9移到8的下面，而“半程”是指9移到7的下面）。

9,8,4,5,6；10,8,6,5,7；9,6,10,5,9；7,4,6,10,8；5,7,6,4,1；2,3,9,7,6；3,2,1,4,8；10,5,3,6,8；2,9,7,8,6；3,10,2,9,1；4,2,9,7,8；6,3,10,9,2；4,1,8,7,6；3,2,7,8,1；4,7,5,9,10；2,8,7,5,10；2。

在对华容道的典型开局式——“横刀立马”的解法进行介绍之后，让我们来讨论一下华容道的开局式问题。

造成华容道开局式多样性的原因是它有5个矩形块，矩形块可以横放，也可以竖放。可以只让一个横放，其他4个竖放；也可以只让一个竖放，其他4个横放；或者取其他组合，甚至让5个都横放。只有让5个都竖放是不可取的。根据有几个矩形块横放，开局式可分一横式、二横式、三横式、四横式、五横式共5大类。在每一大类中，除了五横式只有一种布局外，其他大类每个又都有多种可能的开局式。我国华容道专家齐尧教授（原北京工业学院副院长）曾总结、提炼出180种开局式。

我们对开局式有下列约定俗成的规定：①一般都把曹操置于上方中央；②如果某一种布局是另一布局经移动若干棋子后形成的，则不认为它是一种合格的开局式，也就是说两种开局式原则上是“不互通的”；③对矩形块和小方块则要求它们布置得较有规律，使留下的空格对棋盘的纵轴是对称的。

不是所有的开局式都能解开，除了五竖式明显不可解、五横式只有一种开局式且可解以外，从一横式到四横式都有一些不能解的开局式。什么样的开局式可解？什么样的开局式不可解？有多少开局式可解？有多少开局式不可解？至今仍无人能明确回答，不像“重排九宫”和“重排十五”那样，可根据其排列的奇偶性判定。图1-14到图1-18是一些开局式的例子。