- 曹操逃出走法最难138步，最易0步
- 镜影走法最难165步，最易0步
- 倒影走法最难262步，最易1步
- 反影走法最难268步，最易16步
- 最长最短路径268步
- 严格镜影最难239步，最易50步
- 严格倒影最难283步，最易71步
- 严格反影最难282步，最易48步
- 严格最长最短路径287步
Saturday, November 29, 2008
华容道之最（十）结语
用一天的时间写到了这里，目前我对华容道也只了解到这里。总结一下吧：
华容道之最（九）最简单的严格镜像玩法
说了那么多最难的，也该找几个最简单的来看看了。
最简单的严格镜影，50步，一共有25种，这是其中之一：
最简单的严格倒影，71步，一共有73种，这是其中之一：
最简单的严格反影，48步，一共有30种，这是其中之一：
值得一提的是所有最简单的严格镜像玩法都是五横的布局。
最简单的严格镜影，50步，一共有25种，这是其中之一：
最简单的严格倒影，71步，一共有73种，这是其中之一：
最简单的严格反影，48步，一共有30种，这是其中之一：
值得一提的是所有最简单的严格镜像玩法都是五横的布局。
华容道之最（八）最难的严格镜像玩法
好吧，猜对了，最难的还就是小兵探路。
结论很简单，但为了得出这个结论，我搜索了1,354,392,637,781个节点，3000小时左右的CPU time……我相信一定会有比暴力搜索更好更快的办法。我也相信这三个数字是对的，遗憾的是目前还没有在网上找到过其他人的结论，没法互相验证。
和镜像玩法类似的，搜索也得出了在这种严格意义下的最长的最短路径，仍然是小兵探路的这两种布局，但步数不再是任何一种镜像了。下面这张图就是其中的一种情况，从左边走到右边一共需要287步，比严格倒影和严格反影稍微多一点。
- 最难严格镜影：239步
- 最难严格倒影：283步
- 最难严格反影：282步
结论很简单，但为了得出这个结论，我搜索了1,354,392,637,781个节点，3000小时左右的CPU time……我相信一定会有比暴力搜索更好更快的办法。我也相信这三个数字是对的，遗憾的是目前还没有在网上找到过其他人的结论，没法互相验证。
和镜像玩法类似的，搜索也得出了在这种严格意义下的最长的最短路径，仍然是小兵探路的这两种布局，但步数不再是任何一种镜像了。下面这张图就是其中的一种情况，从左边走到右边一共需要287步，比严格倒影和严格反影稍微多一点。
华容道之最（七）严格镜像玩法
镜像的问题也解决了，从任何一个布局到另一个布局，最难也就是268步了，还有更复杂的吗？回答是肯定的。请看下面这两个布局：
看起来是一模一样的，再仔细看看，原来是左下角的两个小兵交换了位置。之前我们的讨论里同一种棋子之间是等价的，在这种前提下是上图其实是一个布局。从现在往后，我们就不仅要区分不同种类的棋子，还要区分同一种类的不同棋子。
在“区分棋子”这一前提下的镜像玩法，称之为严格镜像玩法。下面的两个图中，左边才是小兵探路的严格镜影，右边的不是，因为右下角姜维和周仓的位置反了。
看起来是一模一样的，再仔细看看，原来是左下角的两个小兵交换了位置。之前我们的讨论里同一种棋子之间是等价的，在这种前提下是上图其实是一个布局。从现在往后，我们就不仅要区分不同种类的棋子，还要区分同一种类的不同棋子。
在“区分棋子”这一前提下的镜像玩法，称之为严格镜像玩法。下面的两个图中，左边才是小兵探路的严格镜影，右边的不是，因为右下角姜维和周仓的位置反了。
很自然的，严格镜影、严格倒影和严格反影，最难能难到什么程度？大胆地猜一下吧，会是小兵探路吗？
华容道之最（六）最难的镜像玩法
要回答“最难的镜像玩法”这个问题，实在是没有什么取巧的办法，我只好老老实实把90981种布局挨个搜索一遍，最后的结果也很有意思：
最难的镜影玩法：165步，只有这一种：
最难的倒影玩法：262步；最难的反影玩法：268步，都是只有两种，而且就是三横最难的布局小兵探路和它的一个变种：
还有一个“最难”顺便也列在这里，从任意一个布局到另一个布局（可能是曹操逃出，可能是三种镜像，也可能是随便的一个别的什么）的最短路径，最长是多少呢？答案非常凑巧，就是从小兵探路走到它的反影，268步。也就是说，从任何一个布局开始，最远只能走出268步不重复的，走到269步必然绕回到之前的某一步。为什么反影刚好就是最的最短路径呢？这是一个很有趣的问题，我倾向于认为这是一个巧合，因为对于大部分的布局来说，走得最远的终局并不是反影。
等有时间我想画出一张镜影、倒影、反影、最长最短路径的曲线图来看看，应该是很有意思的。
顺便说一下，所有布局之间最长的最短路径，可以类比为图论中图的直径，求这一值并不需要挨个搜索所有的节点的最长路径。有一个办法是从任意一个布局A出发，广度优先搜索，求出从这一布局出发的最长最短路径，比如最长可以到达B，然后从B出发，再广度优先搜索一遍，比如最长到C，那么BC之间就是所有布局之间最长的最短路径了。如果A可以同时到达多个B的话，每个B都要搜一遍。能这么做的前提是所有的节点必须是连通的。这也很容易解决，可以每搜过一个布局就做一下记号，下一轮再从没做过记号里面取一个A出来，一直到所有90981种布局都做过记号。用这种办法，我原来要运行两个多小时的暴力搜索，现在只要几秒钟就出结果了。
最难的镜影玩法：165步，只有这一种：
最难的倒影玩法：262步；最难的反影玩法：268步，都是只有两种，而且就是三横最难的布局小兵探路和它的一个变种：
还有一个“最难”顺便也列在这里，从任意一个布局到另一个布局（可能是曹操逃出，可能是三种镜像，也可能是随便的一个别的什么）的最短路径，最长是多少呢？答案非常凑巧，就是从小兵探路走到它的反影，268步。也就是说，从任何一个布局开始，最远只能走出268步不重复的，走到269步必然绕回到之前的某一步。为什么反影刚好就是最的最短路径呢？这是一个很有趣的问题，我倾向于认为这是一个巧合，因为对于大部分的布局来说，走得最远的终局并不是反影。
等有时间我想画出一张镜影、倒影、反影、最长最短路径的曲线图来看看，应该是很有意思的。
顺便说一下，所有布局之间最长的最短路径，可以类比为图论中图的直径，求这一值并不需要挨个搜索所有的节点的最长路径。有一个办法是从任意一个布局A出发，广度优先搜索，求出从这一布局出发的最长最短路径，比如最长可以到达B，然后从B出发，再广度优先搜索一遍，比如最长到C，那么BC之间就是所有布局之间最长的最短路径了。如果A可以同时到达多个B的话，每个B都要搜一遍。能这么做的前提是所有的节点必须是连通的。这也很容易解决，可以每搜过一个布局就做一下记号，下一轮再从没做过记号里面取一个A出来，一直到所有90981种布局都做过记号。用这种办法，我原来要运行两个多小时的暴力搜索，现在只要几秒钟就出结果了。
再顺便说一下，最简单的镜影是0步，最简单的倒影是1步，这两个都很容易列举；最简单的反影则是16步，一共有8种，都是五横的布局，下面是其中之一：
华容道之最（五）镜像玩法
现在我们已经知道了华容道最难的开局，知道了所有可能的开局，甚至每一个开局的最优解法都有了，华容道是不是就没有秘密了呢？回答是：还才刚上路呢！
之前我们探讨的都是华容道的经典走法，也就是曹操走到出口就算胜利了。当然如果出口的位置变一下，比如变成左下角，就会衍生出新的玩法，但总归还是局限在把某一个棋子移动到某一个特定的位置。如果进一步呢，比如要求每个棋子都要移动到指定的位置呢？也就是同时指定了开始和结束的布局，要找出这两个布局之间的最短路径。这样就不能只考虑曹操了，所有的棋子都要照顾到，难度一下子就大了好多。
这种推广的玩法并不是我首创，在黄志华先生这篇文章里介绍了泰式玩法，就是从一个指定的布局到另一个指定的布局。经典的“曹操逃出”玩法只是这种推广的玩法的一个特例罢了。还有几个有意思的特例，就是下面要介绍的镜影（左右对称）、倒影（上下对称）、反影（中心对称/旋转对称）。我这里是借用了黄志华先生的叫法。
下面这张图就是一个例子：峰回路转（左上）及其镜影（右上）、反影（左下）、倒影（右下）。应该不需要再解释什么了。
一般来说，倒影玩法难于镜影，反影又难于倒影，而镜影、倒影、反影这三种玩法一般都比经典的曹操逃出的步数要多。
好了，问题出来了，最难的镜影、倒影、反影需要多少步呢？
之前我们探讨的都是华容道的经典走法，也就是曹操走到出口就算胜利了。当然如果出口的位置变一下，比如变成左下角，就会衍生出新的玩法，但总归还是局限在把某一个棋子移动到某一个特定的位置。如果进一步呢，比如要求每个棋子都要移动到指定的位置呢？也就是同时指定了开始和结束的布局，要找出这两个布局之间的最短路径。这样就不能只考虑曹操了，所有的棋子都要照顾到，难度一下子就大了好多。
这种推广的玩法并不是我首创，在黄志华先生这篇文章里介绍了泰式玩法，就是从一个指定的布局到另一个指定的布局。经典的“曹操逃出”玩法只是这种推广的玩法的一个特例罢了。还有几个有意思的特例，就是下面要介绍的镜影（左右对称）、倒影（上下对称）、反影（中心对称/旋转对称）。我这里是借用了黄志华先生的叫法。
下面这张图就是一个例子：峰回路转（左上）及其镜影（右上）、反影（左下）、倒影（右下）。应该不需要再解释什么了。
一般来说，倒影玩法难于镜影，反影又难于倒影，而镜影、倒影、反影这三种玩法一般都比经典的曹操逃出的步数要多。
好了，问题出来了，最难的镜影、倒影、反影需要多少步呢？
华容道之最（四）布局知多少
华容道之最（三）中得到的开局数目并不是全部布局的数目，因为这些开局都是由可能的终局推演出来的，所以那些“无解”的开局就不包含在里面了。接下来我想知道的就是去除所有的限制以后，华容道的布局总数到底有多少。
求解的思路和前面一样，不同的是要先确定曹操的位置，这一共有12种可能；然后空格的位置不能限定在曹操边上了，但两个空格和四个小兵仍然必须是3黑3白，这中间的可能性一共有C(8,3)C(8,3)种；再从这6个1x1的格子中选出两个空格，这是C(6,2)种；最后是把横子和竖子放进去。
因为不需要移动棋子，程序一下子就简单了许多。最后得到的总数是363494。
当然这里面有一些布局彼此之间是左右对称的，也就是说把布局A左右倒过来就得到了布局B。这样对称的布局对于华容道经典玩法“曹操逃出”的胜利条件来说是等价的，因为出口是在最底一横中间也是对称的，所以如果知道A的解法，每一步都左右倒过来就得到了B的解法。事实上之前的程序在求解的时候都考虑了对称的情况，如果有一个布局的左右对称布局已经求解过了就直接跳过去，可以节省很多时间。刨去左右对称的情况以后，总数是181962。
如果进一步把上下对称和旋转对称也去掉，最后得到的布局数目是90981。这个数字对后面求镜影、倒影和反影的玩法来说，是更根本的。
求解的思路和前面一样，不同的是要先确定曹操的位置，这一共有12种可能；然后空格的位置不能限定在曹操边上了，但两个空格和四个小兵仍然必须是3黑3白，这中间的可能性一共有C(8,3)C(8,3)种；再从这6个1x1的格子中选出两个空格，这是C(6,2)种；最后是把横子和竖子放进去。
因为不需要移动棋子，程序一下子就简单了许多。最后得到的总数是363494。
当然这里面有一些布局彼此之间是左右对称的，也就是说把布局A左右倒过来就得到了布局B。这样对称的布局对于华容道经典玩法“曹操逃出”的胜利条件来说是等价的，因为出口是在最底一横中间也是对称的，所以如果知道A的解法，每一步都左右倒过来就得到了B的解法。事实上之前的程序在求解的时候都考虑了对称的情况，如果有一个布局的左右对称布局已经求解过了就直接跳过去，可以节省很多时间。刨去左右对称的情况以后，总数是181962。
如果进一步把上下对称和旋转对称也去掉，最后得到的布局数目是90981。这个数字对后面求镜影、倒影和反影的玩法来说，是更根本的。
华容道之最（三）最难的布局
横刀立马的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步，如果不在，就查字典，字典里没有的就做一下左右镜像再查，还没有的就是无解了。
说起来还挺复杂的，但在计算机上也就是一秒钟不到结果就出来了。我的程序在这里，有兴趣的朋友可以自己下下来玩玩。
最后揭晓答案吧：最难的布局是“峰回路转”——
最暴力的办法就是构造所有的布局，逐一求解，最后得到的自然就是最难的布局。但这个办法有点笨，而且耗时不少。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步，就这一种：
一横最难93步，就这一种：
两横最难138步，一共三种，参见上面的峰回路转。
三横最难135步，一共两种，这是其中之一小兵探路，后面还会经常用到这个布局：
四横最难97步，一共两种，这是其中之一：
五横最难56步，一共六种，这是其中之一：
华容道之最（二）最经典的布局及定义
华容道的历史我不想在这里多说了，有兴趣的可以参考维基百科或者百度百科的介绍。最经典的布局无疑是下面这个——横刀立马。
就着这个布局我想先明确一下关于华容道的一些定义。不同玩法相关的我会慢慢引入，这里先说一些共同的：
- 棋盘：华容道的棋盘是由五横四纵（4x5）一共二十个方格组成的。
- 棋子：一共有十个棋子。最大的2x2的棋子是曹操，五个1x2或者2x1的棋子是蜀国的五虎上将关羽、张飞、赵云、马超和黄忠，四个1x1的棋子是小兵（图中的四个分别是姜维、魏延、周仓和王平，虽然这些人在赤壁之战的时候还没有到齐，但只是借用一下他们的名字头像，应该无伤大雅吧），还剩下两个1x1的空格。
- 移动：棋子只能在棋盘内滑动，并且只能滑动到相邻的空格中。需要特别注意的是同一个棋子如果一次可以滑动两格，那么只算一步。比如上面的周仓走一格到姜维下面是一步，走两格到魏延下面也是一步；姜维走一格到周仓边上是一步，拐个弯走两格到王平边上也只算一步。这个规则对1x2和2x1的棋子也一样适用，当然1x2和2x1的棋子没法拐弯了。
- 出口：出口在棋盘最下面中间的位置，也就是曹操走到姜维、魏延和两个空格围起来的这个地方就算获胜了。当然对于镜像玩法胜利的条件就不一样了，后面会再说。
横刀立马这一布局里面曹操被蜀国大将重重包围，五虎将里只有关羽一个横的，关二哥使的是八十二斤的青龙偃月刀，这也就是这一布局名字的由来了。曹操要想走出来，就得靠关羽不停的让。也就是所谓的“曹瞒兵败走华容，正与关公狭路逢。只为当初恩义重，放开金锁走蛟龙。”
横刀立马的最优解是81步。第一次有纪录的81步走法是由马丁·加德纳在1964 年2月刊的《科学美国人》给出。用计算机很容易验证这一点，只要使用广度优先搜索，一层层展开所有可能的移动，再剔除掉重复的局面，就很容易找到最优解。
华容道对计算机来说其实复杂度不是很高，看起来有四种十个棋子，每个棋子有四个方向，再考虑到走一格和走两格的情况，每一步细分之下有32种不同的走法，但实际上由于空格只有两个，可能的走法要少得多。就横刀立马这一布局来说，我的程序搜索了11951种局面就找到解了，这对计算机来说规模是很小的。之前看到一篇文章，说担心展开太多，所以采用深度优先搜索来求解，这个担心是没有必要的，反而会花费更多的时间。
目前最普通的计算机，用广度优先算法求解华容道某一个布局的时间应该不到一秒钟。
华容道之最（一）一点历史和由来
小时候在商店里见过华容道玩具，和陆战棋、象棋这些放在一块儿卖的。塑料做的十个棋子上印着曹操和关张赵马黄还有四个小兵的图像。现在回想起来做工是很粗糙的，但在当时小孩们的眼里，仍然是不可多得的一件宝贝。不记得最终是不是拥有过一套，但印象最深的还是隔着玻璃橱窗看到的曹操们。
后来大学的时候学了一点编程，又玩了点三国志游戏，就想着自己做一个华容道试试，还真的成功了。程序是用Visual Basic写的，具体的时间想不起来了，好在当时有给程序做“关于”窗口的习惯，也就是版权页，“华容道3.0，for Windows98，1999.5”，快十年了呵。至于为什么是3.0，回想起来，大约是之前在试验求解算法的时候界面做得很丑，后来算法搞定了就在这上面用了点心思，把三国志五上的图片扒下来做棋子，这中间升级了两次。当时用的机器是赛扬300A的，我的程序求“横刀立马”的最少步数要一分钟，已然很激动和得意了。前几天我把这个程序翻了出来，把不兼容的地方稍微改了改，还能跑，后面文章里的图都是用这个程序生成的。
然后光阴似箭日月如梭，前一阵子不知道为什么又想起华容道了。这时候想的已经不是某个布局最少要多少步走出来，而是华容道最复杂能复杂到什么程度？也就是说一共有多少种可能的布局？最难的一个布局要多少步？很快搜索引擎就把我带到了半瓶墨水的Blog，原来不久前他已经解决了这个问题。从他那里我又逛到黄志华先生的Blog。黄先生对华容道的研究就完全不是我这样的“业余爱好者”可以比拟的了。我很赞同他说的华容道的求解目标不应该局限于“曹操逃出”这一结局，镜影、倒影、反影这些玩法往往更有挑战性。再者，华容道的棋子都是有名字的，比如马超和黄忠，在横刀立马里都是竖向1x2的棋子，如果我们在求镜像的时候要求这些棋子也要一一对应地转过来，就又引出了严格镜影、严格倒影和严格反影这些更难上一层的玩法。再推想开去，我上面那个问题又浮现出来了，从任意一个布局移动到另一个布局(包括镜影等)的最少步数，最大能大到多少呢？
如果从图论的角度来看，一个个布局就相当于节点，这些节点组成了若干个连通无权无向图，最长的最短路径，也就是图的“直径”，求解这一问题应该是很有意思的。我没有办法在数学的角度上解这道题，还是得借助计算机的穷尽搜索。埋头编了几个程序以后，这些答案终于一一浮出水面了。于是我想把它们记录下来，如果后来人有缘看到，也可以做一个参照比对。
后来大学的时候学了一点编程，又玩了点三国志游戏，就想着自己做一个华容道试试，还真的成功了。程序是用Visual Basic写的，具体的时间想不起来了，好在当时有给程序做“关于”窗口的习惯，也就是版权页，“华容道3.0，for Windows98，1999.5”，快十年了呵。至于为什么是3.0，回想起来，大约是之前在试验求解算法的时候界面做得很丑，后来算法搞定了就在这上面用了点心思，把三国志五上的图片扒下来做棋子，这中间升级了两次。当时用的机器是赛扬300A的，我的程序求“横刀立马”的最少步数要一分钟，已然很激动和得意了。前几天我把这个程序翻了出来，把不兼容的地方稍微改了改，还能跑，后面文章里的图都是用这个程序生成的。
然后光阴似箭日月如梭，前一阵子不知道为什么又想起华容道了。这时候想的已经不是某个布局最少要多少步走出来，而是华容道最复杂能复杂到什么程度？也就是说一共有多少种可能的布局？最难的一个布局要多少步？很快搜索引擎就把我带到了半瓶墨水的Blog，原来不久前他已经解决了这个问题。从他那里我又逛到黄志华先生的Blog。黄先生对华容道的研究就完全不是我这样的“业余爱好者”可以比拟的了。我很赞同他说的华容道的求解目标不应该局限于“曹操逃出”这一结局，镜影、倒影、反影这些玩法往往更有挑战性。再者，华容道的棋子都是有名字的，比如马超和黄忠，在横刀立马里都是竖向1x2的棋子，如果我们在求镜像的时候要求这些棋子也要一一对应地转过来，就又引出了严格镜影、严格倒影和严格反影这些更难上一层的玩法。再推想开去，我上面那个问题又浮现出来了，从任意一个布局移动到另一个布局(包括镜影等)的最少步数，最大能大到多少呢？
如果从图论的角度来看，一个个布局就相当于节点，这些节点组成了若干个连通无权无向图，最长的最短路径，也就是图的“直径”，求解这一问题应该是很有意思的。我没有办法在数学的角度上解这道题，还是得借助计算机的穷尽搜索。埋头编了几个程序以后，这些答案终于一一浮出水面了。于是我想把它们记录下来，如果后来人有缘看到，也可以做一个参照比对。
Saturday, November 22, 2008
Subscribe to:
Posts (Atom)