Saturday, November 29, 2008

华容道之最(三)最难的布局

横刀立马的81步解法说多不多,说少还是不少的。事实上在计算机介入之前,从一百步左右一点点减少到最后走到81步,还是让很多聪明人绞尽了脑汁。解开横刀立马之后,我想知道的下一个,就是这么多布局中,最难的,也就是最少步数最多的布局,是哪一个?

最暴力的办法就是构造所有的布局,逐一求解,最后得到的自然就是最难的布局。但这个办法有点笨,而且耗时不少。Google Group的这个帖子里,有一个非常聪明的办法,就是先构造所有可能的终局,然后一层层反推,得到所有的可能的开局,在最底层的,自然就是最难的布局。而且通过这种做法很容易得出一个包含所有布局求解路径的“字典”,有了这个字典,我们以后求解就不需要再搜索,直接查字典就行了!

这个思路确实太棒了。具体来说呢,首先在终局的时候曹操是确定的,然后空格的位置也只有下面两种情况(4代表曹操,0代表空格):
????     ????
????     ????
????     ?00?
044?     ?44?
044?     ?44?
因为最后一步一定走的是曹操,所以空格必然在曹操周围,只有上、左、右三种情况,左右又是对称的没必要重复算,就只有上面的两种了。

接下来要把四个小兵填进去。看起来像是有C(14,4)=1001种填法,但其实没这么多。因为后面剩下的都是2格的棋子,如果把棋盘涂成国际象棋那样的黑白两色,一共10黑10白,曹操占了2黑2白,空格如上所示也必然是1黑1白,五虎将必然是5黑5白,所以四个小兵必然是2黑2白。所以可能的填法是C(7,2)C(7,2)=441种,少了一多半。

再来就是把五虎将填进去。前5个棋子都确定了以后,五虎将的填法没多少的,因为很多地方都被卡死了,经常只有一两种填法。

这样求出来的所有“可能”的终局是684个。注意到这里说的是可能的终局,我们其实把那些一开始曹操就已经在出口的情况排除掉了。而且这里面去掉了左右对称的重复部分,也就是说如果终局A通过左右对称交换能得到终局B,那么A和B两个只保留一个。

接下来就没啥技巧了,把这684个终局作为第0层,穷举所有走法得到第1层,继续往下广度优先搜索,走到头了也就得到结果了。记得每次要把指向父节点的指针存下来,这样就可以构造出一个求解字典了,以后再求解只要沿着父指针一直走,就走到终局了,而且肯定是最短路径。

最后得到的字典由121969个布局组成,其中包含了684个终局,同样也剔除了左右镜像。当然这个字典没有包括所有的情况,所以在使用的时候必须先判断曹操是不是已经在出口了,如果在,直接就返回0步,如果不在,就查字典,字典里没有的就做一下左右镜像再查,还没有的就是无解了。

说起来还挺复杂的,但在计算机上也就是一秒钟不到结果就出来了。我的程序在这里,有兴趣的朋友可以自己下下来玩玩。

最后揭晓答案吧:最难的布局是“峰回路转”——


一个共需要138步才能把曹操走出来。剔除镜像对称以后,一共有3种布局的解法是138步,可以称之为峰回路转的3个变种吧。另外两种可以看这里

注意到峰回路转是两横三竖,而五虎将的布局有五竖、一横四竖、两横三竖、三横两竖、四横一竖、五横这六种情况,两横的最难布局显然就是上面的峰回路转了,那其他几种情况最难的是什么样的呢?

五竖最难19步,一共两种,这是其中之一:

一横最难93步,就这一种:


两横最难138步,一共三种,参见上面的峰回路转。

三横最难135步,一共两种,这是其中之一小兵探路,后面还会经常用到这个布局:

四横最难97步,一共两种,这是其中之一:

五横最难56步,一共六种,这是其中之一:

No comments: