华容道有多少种开局？最难的华容道开局是哪个？(1)
华容道游戏存在很久了，但是，有两个问题还没有答案：
1. 华容道游戏到底有多少可以求解的开局？
2. 最难解的华容道开局又是哪个（或者，哪些个）？
智取华容道的在线游戏上线两个月了，现在已经有了95个关卡，三千两百七十多个过关记录。
当初做这个游戏，实际上经过一番挣扎，到底要不要做，看到网上贴的很多秘籍，转来贴去，很多都看不懂，还有很多都并非最佳解法，还是忍不住做了这么一个在线游戏，收集已知的名局。
随着自动解题程序的上线，我对华容道的兴趣开始转移。在我的列表里面，想做的事情已经排到了我40岁以后，还要努力养家糊口，所以注定有一些感兴趣的事情做不完。
但是这次选择华容道来做，确实学到了不少东西，所以在兴趣还没有完全缺失以前，还是想再多走一步。
前面提到的那两个问题，用程序求解应该不困难，为什么到现在还没有答案呢？
非不可为，实不为也。
那么，就让我来搞定这个问题吧！半瓶墨水也要写出大千世界 
讨论参见：http://groups.google.com/group/pongba/browse_thread/thread/a49ec9fd9541e28f
现在进展：
1. 已找出所有可能的终局：684个，代码参见 http://www.fayaa.com/code/view/453/
2. 由终局已经推出华容道所有可求解的开局数量，含镜像263977种，不含镜像132156种
代码参见：http://www.fayaa.com/code/view/457/
所以第一个问题已经搞定了，关于第二个问题，代码已经完成大半了
估计这个周末就能搞定，请静待最难开局的出现吧！
附：已知的最难开局是峰回路转，最快需要138步，很可能就是它了。
Update@2008/11/01，22:44PM:
最新数据表明：“峰回路转”开局已是最难开局，过几天搞一些有意思的分析结果出来看看。
Loading ...
共 9 条评论
发表评论
Additional comments powered by BackType
最新数据表明：“峰回路转”开局已是最难开局，过几天搞一些有意思的分析结果出来看看。
Hi, 你好！
我看了你的文章和Google Group里的讨论，自己编了个C程序算了一下，得到一些结果挺有意思的。
可能的终局数目和你的一致，不含镜像对称684个。
可能的开局数目我的结果是不含镜像121969。比你的少一万多。
我比较了一下结果，发现如果去掉曹操已经就位的终局，就一样了，都是121285。
我的121969里面只包含了684个终局，而你的132156里面还包含了从这684个终局里面推演出来的其他一万多个终局。
但这样算“所有可求解的开局数量”是不够完备的。因为还有一部分开局无法从那684个终局走到，这点是因为计算这个684的时候限定死了空格只能在曹操的左边或者上边，我怀疑这种限制有可能导致一些终局永远不可能被走到，比如
0133
3333
3311
1442
0442
就不在你的132156里面。
如果要把所有这些终局都包含在内的话，我算出来的结果是：终局12449，开局（含终局）数目是133734。
当然这些对最难开局峰回路转138步，不含终局的开局数目121285等结论没有影响。
@cyang
你说的没有错，这个问题一直存在，
最初写着这个只为了找出最难的，最后发现居然就是峰回路转的时候，就失去了兴趣，所以我一直没有去管它
@cyang 另外我在google group里面的的讨论里面有一个假设，即：曹操是要走出来的，即曹操不能在出口处，如果按照这个标准来看，或许少一些才恰当
最后构造出来的求解字典还是需要684+121285个布局的，其他的就不用了，在查字典之前先判断一下就行了。
我现在的程序是C编的，从构造终局、反推所有开局到生成全部布局的求解字典，在我的机器上不到一秒钟就搞定了。比起早年用VB求解横刀立马都要一分钟，实在是爽！
当然一则是机器速度快了，二来我调了GNU的libavl做快速搜索插入，在这个问题上加速很多。
@cyang 呵呵不错啊，能在这儿贴一下代码吗？
http://www.fayaa.com/code/
贴上来了，请多指教.gif)
http://www.fayaa.com/code/view/497/
半瓶墨水：你好
关于华容道游戏到底有多少可以求解的开局？请你看一下，这两篇 blog 文章 http://blog.chinaunix.net/u3/91750/showart_1806708.html
http://blog.chinaunix.net/u3/91750/showart_1830027.html
要比前面提到的数字大的多。
用程序测算得到开局场景“338700”个这个意想不到的数。
其中包括：
对称场景 330 个，
镜像场景 169185 个，
正像场景应该有 169515 个
目前我正在作非标（无将 至 七将，五将为传统标准的）的场景数据库。用数据库作场景浏览器；用数据库搜索玩家创作的开局是不是新创，也蛮有意思的。
2009年3月8日
@自然牛
我去除了镜像局和无解开局