华容道之最（二）最经典的布局及定义

华容道的历史我不想在这里多说了，有兴趣的可以参考维基百科或者百度百科的介绍。最经典的布局无疑是下面这个——横刀立马。

就着这个布局我想先明确一下关于华容道的一些定义。不同玩法相关的我会慢慢引入，这里先说一些共同的：

• 棋盘：华容道的棋盘是由五横四纵（4x5）一共二十个方格组成的。
• 棋子：一共有十个棋子。最大的2x2的棋子是曹操，五个1x2或者2x1的棋子是蜀国的五虎上将关羽、张飞、赵云、马超和黄忠，四个1x1的棋子是小兵（图中的四个分别是姜维、魏延、周仓和王平，虽然这些人在赤壁之战的时候还没有到齐，但只是借用一下他们的名字头像，应该无伤大雅吧），还剩下两个1x1的空格。
• 移动：棋子只能在棋盘内滑动，并且只能滑动到相邻的空格中。需要特别注意的是同一个棋子如果一次可以滑动两格，那么只算一步。比如上面的周仓走一格到姜维下面是一步，走两格到魏延下面也是一步；姜维走一格到周仓边上是一步，拐个弯走两格到王平边上也只算一步。这个规则对1x2和2x1的棋子也一样适用，当然1x2和2x1的棋子没法拐弯了。
• 出口：出口在棋盘最下面中间的位置，也就是曹操走到姜维、魏延和两个空格围起来的这个地方就算获胜了。当然对于镜像玩法胜利的条件就不一样了，后面会再说。

横刀立马这一布局里面曹操被蜀国大将重重包围，五虎将里只有关羽一个横的，关二哥使的是八十二斤的青龙偃月刀，这也就是这一布局名字的由来了。曹操要想走出来，就得靠关羽不停的让。也就是所谓的“曹瞒兵败走华容，正与关公狭路逢。只为当初恩义重，放开金锁走蛟龙。”

横刀立马的最优解是81步。第一次有纪录的81步走法是由马丁·加德纳在1964 年2月刊的《科学美国人》给出。用计算机很容易验证这一点，只要使用广度优先搜索，一层层展开所有可能的移动，再剔除掉重复的局面，就很容易找到最优解。

华容道对计算机来说其实复杂度不是很高，看起来有四种十个棋子，每个棋子有四个方向，再考虑到走一格和走两格的情况，每一步细分之下有32种不同的走法，但实际上由于空格只有两个，可能的走法要少得多。就横刀立马这一布局来说，我的程序搜索了11951种局面就找到解了，这对计算机来说规模是很小的。之前看到一篇文章，说担心展开太多，所以采用深度优先搜索来求解，这个担心是没有必要的，反而会花费更多的时间。

目前最普通的计算机，用广度优先算法求解华容道某一个布局的时间应该不到一秒钟。

至于具体81步怎么走呢？我想推荐半瓶墨水的“智取华容道”在线游戏，用自定义关卡把布局输入进去，就可以求解了。