华容道有多少种开局?最难的华容道开局是哪个?(1)

作者:半瓶墨水   链接:http://www.2maomao.com/blog/hrd-openings-and-hardest/

=====================================
插播一则广告

发芽网华容道精装版App发布啦(iPhone和iPad版), 点击查看
https://itunes.apple.com/cn/app/fa-ya-wang-hua-rong-dao-jing/id599917734

还是一样的精装版,一样的过关记录回放,精致的过关特效,方便的操作,精美的配乐。
包含发芽网华容道在线版的所有布局以及许多首手机程序独有的布局。
=====================================

华容道游戏存在很久了,但是,有两个问题还没有答案:
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:
最新数据表明:“峰回路转”开局已是最难开局,过几天搞一些有意思的分析结果出来看看。

9 条评论 发表在“华容道有多少种开局?最难的华容道开局是哪个?(1)”上

  1. 半瓶墨水说道:

    最新数据表明:“峰回路转”开局已是最难开局,过几天搞一些有意思的分析结果出来看看。

  2. cyang说道:

    Hi, 你好!
    我看了你的文章和Google Group里的讨论,自己编了个C程序算了一下,得到一些结果挺有意思的。

    可能的终局数目和你的一致,不含镜像对称684个。
    可能的开局数目我的结果是不含镜像121969。比你的少一万多。
    我比较了一下结果,发现如果去掉曹操已经就位的终局,就一样了,都是121285。
    我的121969里面只包含了684个终局,而你的132156里面还包含了从这684个终局里面推演出来的其他一万多个终局。

    但这样算“所有可求解的开局数量”是不够完备的。因为还有一部分开局无法从那684个终局走到,这点是因为计算这个684的时候限定死了空格只能在曹操的左边或者上边,我怀疑这种限制有可能导致一些终局永远不可能被走到,比如
    0133
    3333
    3311
    1442
    0442
    就不在你的132156里面。
    如果要把所有这些终局都包含在内的话,我算出来的结果是:终局12449,开局(含终局)数目是133734。

    当然这些对最难开局峰回路转138步,不含终局的开局数目121285等结论没有影响。

  3. 半瓶墨水说道:

    @cyang
    你说的没有错,这个问题一直存在,
    最初写着这个只为了找出最难的,最后发现居然就是峰回路转的时候,就失去了兴趣,所以我一直没有去管它

  4. 半瓶墨水说道:

    @cyang 另外我在google group里面的的讨论里面有一个假设,即:曹操是要走出来的,即曹操不能在出口处,如果按照这个标准来看,或许少一些才恰当

  5. cyang说道:

    最后构造出来的求解字典还是需要684+121285个布局的,其他的就不用了,在查字典之前先判断一下就行了。

    我现在的程序是C编的,从构造终局、反推所有开局到生成全部布局的求解字典,在我的机器上不到一秒钟就搞定了。比起早年用VB求解横刀立马都要一分钟,实在是爽! 😀 当然一则是机器速度快了,二来我调了GNU的libavl做快速搜索插入,在这个问题上加速很多。

  6. 半瓶墨水说道:

    @cyang 呵呵不错啊,能在这儿贴一下代码吗?
    http://www.fayaa.com/code/

  7. cyang说道:

    贴上来了,请多指教 🙂

    http://www.fayaa.com/code/view/497/

  8. 自然牛说道:

    半瓶墨水:你好
    关于华容道游戏到底有多少可以求解的开局?请你看一下,这两篇 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日

  9. 半瓶墨水说道:

    @自然牛
    我去除了镜像局和无解开局

留下回复