如何生成华容道开局的所有组合？

[realfun]

做了华容道在线解题程序之后，就想遍历所有开局，找出真正不重复的开局
到目前为止还没有找出有效地生成所有开局的方法：

开局的定义（参见:http://www.fayaa.com/youxi/hrd/#game-spec)：
4x5的格子，必须由10个方块组成
-- 1个2x2方块(曹操)，称之为Block
-- 5个两格方块(大将，可横可竖)，称之为HV，横为H，竖为V
-- 4个一格方块(小兵)，称之为Dot
-- 2个空白小块

附件里这张图是最常见的开局：横刀立马

我的想法是，按照Block -> HV -> Dot这样的摆放顺序来求组合
Block有12种摆放位置
然后HV摆完就只剩6个空位置了，C(16, 6) = 8008 （由于排列的限制，很可能比这个小，甚至小一个数量级）
HV的组合有H0V5 -> H5V0，共6种可能性
然后Dot摆完，就只剩下2个空位置了，C(6, 2) = 15
12 * 6 * 15 * 8008 = 8648640

也就是说，最多只可能有8648640种组合
但是有效的怎么生成他们呢？又怎么在生成的过程中避免重复以及无效的布局呢？
至今没想到有效地办法，主要是卡在HV的处理上

有没有什么想法?

--
代码发芽网： http://www.fayaa.com/code/ （无需插件支持blog代码高亮，100+种语言，30+种高亮主题）
游戏发芽网： http://www.fayaa.com/youxi/ （华容道等在线小游戏）
我的Blog: 半瓶墨水(http://www.2maomao.com/blog)

[Eric]

根据我做一个类似问题的经验， 这样算出来的这个值是非常大的。实际上随着放的方块越来越多， 后面的可能位置会越来越少的， 所以可能性没有想的那么
多， 估计在

12＊100-1000 的量级

四个小方块和空白可以暂时不加区分， 到时候往里面填的时候规定一下等价关系。

在不放小方块和空白的时候， 先把开局做出来。 然后我们看看有多少个，再想想等价关系， 我觉得这样比较好。

[spell scroll]

2008/10/24 realfun <rea...@gmail.com>

做了华容道在线解题程序之后，就想遍历所有开局，找出真正不重复的开局
到目前为止还没有找出有效地生成所有开局的方法：

开局的定义（参见:http://www.fayaa.com/youxi/hrd/#game-spec)：
4x5的格子，必须由10个方块组成
-- 1个2x2方块(曹操)，称之为Block
-- 5个两格方块(大将，可横可竖)，称之为HV，横为H，竖为V
-- 4个一格方块(小兵)，称之为Dot
-- 2个空白小块

我的想法是，按照Block -> HV -> Dot这样的摆放顺序来求组合
Block有12种摆放位置
然后HV摆完就只剩6个空位置了，C(16, 6) = 8008 （由于排列的限制，很可能比这个小，甚至小一个数量级）
HV的组合有H0V5 -> H5V0，共6种可能性
然后Dot摆完，就只剩下2个空位置了，C(6, 2) = 15
12 * 6 * 15 * 8008 = 8648640

也就是说，最多只可能有8648640种组合
但是有效的怎么生成他们呢？又怎么在生成的过程中避免重复以及无效的布局呢？
至今没想到有效地办法，主要是卡在HV的处理上

有没有什么想法?

(1) 将格子间错地染上黑白两色
(2) 根据对称性, 曹操的位置减为4种
(3) 摆好曹操后, 剩下16个位置.8黑8白
(4) 因为H,V两种形状填充的黑白数目相同,
所以小兵和空格必然3黑3白.  (必要但不充分)
(5) 暂时不区分小兵和空格, 最多有C(8,3)*C(8,3)
所以上限最多有4*C(8,3)*C(8,3) = 4*56*56=12544, 可以写个程序暴力填充看看.



--
http://spellscroll.com
数学题概率题算法题编程题智力题

[realfun]

呵呵很不错的想法，离散数学里面国际象棋的马踏棋盘好像就用到了黑白两色的方法

对称性的想法很好，不过就算再加上曹操不可能在出口，也只能减为7种可能性
剩下的四个小方块是C(6,4)
7*C(8,3)*C(8,3)*C(6,4) = 329280

然后对于C(8,3)*C(8,3)中的每一个，都可能是H0V5 -> H5V0中的组合，共6种
329280*6=1975680

然后呢，还少算了一些，对于非H0V5和H5V0的情况，比如H2V3，则对于C(8,3)*C(8,3)中的每一个，可能有许多种排放方式

所以我觉得最不好弄的就是最后说的这个H/V的组合

[spell scroll]

2008/10/25 realfun <rea...@gmail.com>

呵呵很不错的想法，离散数学里面国际象棋的马踏棋盘好像就用到了黑白两色的方法

  马踏棋盘?  能具体说说什么问题码? 遍历棋盘的步数? 可能走法数目?

对称性的想法很好，不过就算再加上曹操不可能在出口，也只能减为7种可能性

 OK. 原来上下是不对称的. :-)

剩下的四个小方块是C(6,4)
7*C(8,3)*C(8,3)*C(6,4) = 329280

然后对于C(8,3)*C(8,3)中的每一个，都可能是H0V5 -> H5V0中的组合，共6种
329280*6=1975680

然后呢，还少算了一些，对于非H0V5和H5V0的情况，比如H2V3，则对于C(8,3)*C(8,3)中的每一个，可能有许多种排放方式

所以我觉得最不好弄的就是最后说的这个H/V的组合

不是很明白你说的这个H/V组合. 我觉得一旦曹操,小兵,空格定好了之后,留给五虎上将的可能卡位就不多了吧 .
比如 在你http://www.fayaa.com/youxi/hrd/, 前10个开局里只有3,7,8,9有很有限的几种选择, 其他的都是唯一的.

--
http://spellscroll.com
数学题概率题算法题编程题智力题

[realfun]

"不是很明白你说的这个H/V组合. 我觉得一旦曹操,小兵,空格定好了之后,留给五虎上将的可能卡位就不多了吧 "
是不多，但是你怎么把这些"可能卡位"找出来呢？不是一样要先找出所有的情况然后消除掉无效的卡位？

我也知道最后有效地布局不会很多，但是要做一个千万级的布局过滤也不是很容易的

所以我才会想有什么方式可以在生成的时候就减少这种无效布局

2008/10/25 spell scroll <spell...@gmail.com>

--

[wangmao]

2008/10/25 realfun <rea...@gmail.com>

"不是很明白你说的这个H/V组合. 我觉得一旦曹操,小兵,空格定好了之后,留给五虎上将的可能卡位就不多了吧 "

其实有个更简单的做法，你可以从所有合法的结束局面倒推起，可以找到所有合法的局面了^_^

[realfun]

哇塞，这真是个绝妙的想法
"所有合法的结束局面"，我再细化一下看看

2008/10/25 wangmao <lwm...@gmail.com>

2008/10/25 realfun <rea...@gmail.com>

"不是很明白你说的这个H/V组合. 我觉得一旦曹操,小兵,空格定好了之后,留给五虎上将的可能卡位就不多了吧 "

其实有个更简单的做法，你可以从所有合法的结束局面倒推起，可以找到所有合法的局面了^_^

[Eric]

realfun

我觉得量级真的不大, 因为我做实际问题比你这个大两个量级, C也是几分钟出来了. (我做的问题叫做 Rectangle Packing, 就是
问很多小方块能不能放到一个大矩形里面, 如果能, 把组合输出来)
我觉得性能往往出现在想不到的地方, 不如先做. 一百万并不是大数字, 我常常有一百万大小的字典在python里面.

When in doubt, use brute force

倒推也是非常好的办法, 倒推中最难的是定一个步数的上界.

用 约束满足问题 (Constraint Sat) 的思想, 你应该先放曹操, 再放上将, 再放小兵, 这样减去的枝最多. 先放小兵会出现很多
dead end, 你需要多一次计算才能判断 dead end.

[realfun]

多谢你的建议
我正在尝试倒推法，已差不多证实可行了
两个步骤
1. 枚举所有终局，这个不会太多，明天程序写完就会有实际数据了
2. 倒推出所有开局，倒推的过程就是求解过程，应为方块的移动是可逆的

倒推的时候采用广度优先，应该不会太多，我估计倒推出来的开局应该在10万左右（不包括镜像）

2008/10/25 Eric <xu.ma...@gmail.com>

[realfun]

不是摆完，是千万，而且其中HV的组合很难弄，所以现在开始用倒推法
倒推法的好处在于其生成过程就避免了无效开局

2008/10/25 Eric <xu.ma...@gmail.com>

[Eric]

倒推的确是有效的. 而且倒推的结果你可以存一个字典, 这样每一步到 goal 最少多少步你也可以使用 一个简单的 Dynamic
Programming 求到.

有了每一步到 goal 的距离, 你就有了一个完美的 heuristic function, 一个A* Search 就可以最快的求出问题的解
了, 因此倒推的确是一举三得的事情.

我觉得问题的规模应该和 8-puzzle 差不多大. 8puzzle 我用 python 倒推, 上限是 25 步, 耗时 8秒. 华容道应该
更加长.

另外, 我想了一下, 定义等价是一个烦人的事情, 比如方块移动一步算不算等价, 怎样划分等价. 最后可能通过等价关系缩减状态才是问题的要
点.

[realfun]

呵呵，倒推以后就不需要求解了
因为所有最终局广度优先倒推出的树中每个节点都是有效的开局，否则就是无效的
每个节点上只需要记录父节点以及当前的level
这样再求解的话不就是查表嘛

2008/10/25 Eric <xu.ma...@gmail.com>

[realfun]

忘记说明了，因为使用的是广度优先，"当前的level"就是"到goal最少多少步"

2008/10/25 realfun <rea...@gmail.com>

[spell scroll]

2008/10/25 realfun <rea...@gmail.com>

"不是很明白你说的这个H/V组合. 我觉得一旦曹操,小兵,空格定好了之后,留给五虎上将的可能卡位就不多了吧 "

是不多，但是你怎么把这些"可能卡位"找出来呢？不是一样要先找出所有的情况然后消除掉无效的卡位？

不明白你为什么要不考虑已有的限制而先去凭空列举所有可能的H/V组合??

曹操,小兵,空格定好之后的局面,相当于一个5x4的0-1矩阵,
10个1(曹操,小兵,空格),10个0(准备放五虎上将),现在要解
的问题是对于给定的一个这样的矩阵, 用5个1x2的矩形去填
充10个0的位置,有几种方法?返回值可能是0,1,2,...等等.
我想写个这样的特定程序应该不难 然后你就用这个程序在
7x56x56个可能的矩阵上跑一遍,最后再区分一下小兵和空格.

我也知道最后有效地布局不会很多，但是要做一个千万级的布局过滤也不是很容易的
所以我才会想有什么方式可以在生成的时候就减少这种无效布局

2008/10/25 spell scroll <spell...@gmail.com>

2008/10/25 realfun <rea...@gmail.com>

呵呵很不错的想法，离散数学里面国际象棋的马踏棋盘好像就用到了黑白两色的方法

  马踏棋盘?  能具体说说什么问题码? 遍历棋盘的步数? 可能走法数目?

对称性的想法很好，不过就算再加上曹操不可能在出口，也只能减为7种可能性

 OK. 原来上下是不对称的. :-)

剩下的四个小方块是C(6,4)
7*C(8,3)*C(8,3)*C(6,4) = 329280

然后对于C(8,3)*C(8,3)中的每一个，都可能是H0V5 -> H5V0中的组合，共6种
329280*6=1975680

然后呢，还少算了一些，对于非H0V5和H5V0的情况，比如H2V3，则对于C(8,3)*C(8,3)中的每一个，可能有许多种排放方式

所以我觉得最不好弄的就是最后说的这个H/V的组合

不是很明白你说的这个H/V组合. 我觉得一旦曹操,小兵,空格定好了之后,留给五虎上将的可能卡位就不多了吧 .
比如 在你http://www.fayaa.com/youxi/hrd/, 前10个开局里只有3,7,8,9有很有限的几种选择, 其他的都是唯一的.

--

代码发芽网： http://www.fayaa.com/code/ （无需插件支持blog代码高亮，100+种语言，30+种高亮主题）
游戏发芽网： http://www.fayaa.com/youxi/ （华容道等在线小游戏）
我的Blog: 半瓶墨水(http://www.2maomao.com/blog)

--
http://spellscroll.com
数学题概率题算法题编程题智力题

[spellscroll]

On 10月25日, 下午4时54分, "spell scroll" <spellscr...@gmail.com> wrote:
> 2008/10/25 realfun <real...@gmail.com>

>
> > "不是很明白你说的这个H/V组合. 我觉得一旦曹操,小兵,空格定好了之后,留给五虎上将的可能卡位就不多了吧 "
> > 是不多，但是你怎么把这些"可能卡位"找出来呢？不是一样要先找出所有的情况然后消除掉无效的卡位？
>
> 不明白你为什么要不考虑已有的限制而先去凭空列举所有可能的H/V组合??
>
> 曹操,小兵,空格定好之后的局面,相当于一个5x4的0-1矩阵,
> 10个1(曹操,小兵,空格),10个0(准备放五虎上将),现在要解
> 的问题是对于给定的一个这样的矩阵, 用5个1x2的矩形去填
> 充10个0的位置,有几种方法?返回值可能是0,1,2,...等等.
> 我想写个这样的特定程序应该不难 然后你就用这个程序在
> 7x56x56个可能的矩阵上跑一遍,最后再区分一下小兵和空格.
>

终局情况正好是上面结果的一个子集, 对应着1x56x56个可能的矩阵.

>
> > 我也知道最后有效地布局不会很多，但是要做一个千万级的布局过滤也不是很容易的
> > 所以我才会想有什么方式可以在生成的时候就减少这种无效布局
>
> > 2008/10/25 spell scroll <spellscr...@gmail.com>
>
> > 2008/10/25 realfun <real...@gmail.com>

[spellscroll]

> > 曹操,小兵,空格定好之后的局面,相当于一个5x4的0-1矩阵,
> > 10个1(曹操,小兵,空格),10个0(准备放五虎上将),现在要解
> > 的问题是对于给定的一个这样的矩阵, 用5个1x2的矩形去填
> > 充10个0的位置,有几种方法?返回值可能是0,1,2,...等等.
> > 我想写个这样的特定程序应该不难 然后你就用这个程序在
> > 7x56x56个可能的矩阵上跑一遍,最后再区分一下小兵和空格.
>
> 终局情况正好是上面结果的一个子集, 对应着1x56x56个可能的矩阵.
>

我写了个python程序用我上面的方法计算所有终局的可能(不区分小兵和空格),
得到结果如下:
56x56=3156个所有可能矩阵中只有1075个有解, 并且所有解总数为1652个
计算时间在我笔记本上(Intel T7200 2GHz, 1G RAM) 2.3秒.

程序整理好后我会贴到发芽网.

[spellscroll]

python代码已经贴到
http://fayaa.com/code/view/451/
总共不到100行(包括注释20多行)
优化后, 运行时间从2.3秒降到0.77秒

[medie2005]

像这样的问题，都可以用Knuth的dancing links技巧来处理。对这个问题，还可以考虑对称，以减少计算量。在1秒内应该是不难的。

[realfun]

程序写的没错
呵呵不过这还要再乘上C(6,2)=15，因为四个小点要确定下来
再加上其他6个曹操位置，得到的结果差不多是17万个开局
由开局再算到最佳解，一个10毫秒，需要差不多半小时才能算到结束

呵呵我还是来尝试一下倒推
这两天在家啊带孩子，写的很慢

2008/10/26 spellscroll <spell...@gmail.com>

[realfun]

日，刚写完终局的生成器，尝试recursive yield方式导致的（可以看下面代码的版本1，就是使用recursive yield）
代码着这里：http://www.fayaa.com/code/view/453/
共有804个可能的终局

看看明天有没有时间推出所有开局了

2008/10/26 realfun <rea...@gmail.com>

程序写的没错
呵呵不过这还要再乘上C(6,2)=15，因为四个小点要确定下来
再加上其他6个曹操位置，得到的结果差不多是17万个开局
由开局再算到最佳解，一个10毫秒，需要差不多半小时才能算到结束

呵呵我还是来尝试一下倒推
这两天在家啊带孩子，写的很慢

[realfun]

孩子这两天太闹，只能断断续续的写
生成所有华容道的"可求解"的开局的代码完成了: http://www.fayaa.com/code/view/457/
（速度有些慢，没做任何优化，在我的机器上要跑3-5分钟）
一共有170861种"可求解"的华容道开局，含左右镜像

下一步就是求解者17万种开局啦

2008/10/27 realfun <rea...@gmail.com>

日，刚写完终局的生成器，尝试recursive yield方式导致的（可以看下面代码的版本1，就是使用recursive yield）
代码着这里：http://www.fayaa.com/code/view/453/
共有804个可能的终局

看看明天有没有时间推出所有开局了

[realfun]

前贴结果有误，简化求解逻辑以避免错误，目前的结果应该是对的了：
华容道所有可求解的开局数量，含镜像263977种，不含镜像132156种

写了一篇帖子在这里：
http://www.2maomao.com/blog/hrd-openings-and-hardest/

全求解太慢，debug也不好办，现在求出的结果最难才137步，而实际上峰回路转（ http://www.fayaa.com/youxi/hrd/55/#spec ）是138歩，还需在调试调试

2008/10/30 realfun <rea...@gmail.com>

[Eric]

说实话我从一开始就觉得这个程序应该秒级别的速度的， 为了验证到底快不快， 今天下午写了一个python 程序 程序没有任何优化， 生成全部的
组合只要10秒不到, (包括磁盘IO)

我的所有的开局的数量是 262243, 不知道我哪里没有覆盖到. 我的代码贴发芽上了。

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

如果realfun 兄有空， 我们来对照一下看看我的状态为啥比你的少一些。 （我的结果 dump 成一个字典, key 是 layout 字符
串)

我的最长的是 141 步， 比你的略长。

4 4 1 2
4 4 0 2
0 2 3 3
1 2 3 3
1 1 3 3

你的程序这个只要 137 步， 我检查了我的， 每一步也合法。 所以我觉得可能我忽略掉了一些状态， 而这些状态可能导致捷径。

全求解就是 A* 算法， 有了一个字典， 求解就是查表。

[realfun]

我已经通过完全求解程序证实了"峰回路转"是最长的
你的这个开局是135步，你可以到这里看看，我写了在线求解程序：http://www.fayaa.com/youxi/hrd/add/
（注意：默认选择曹出规则，不要改，其他的是为华容道爱好者用的）

至于开局的数量，我一开始写的程序用C++，很快，但是结果总不对，后来用Python，也写了一个很快的，结果也总对不上
后来只好采用比较简单的解决方案，力图让自己一个月以后还能够看得懂，这样终于找出问题所在
你可以对比我的结果看看，你的答案或许是对的也说不定，因为我把终局也加上了

2008/11/4 Eric <xu.ma...@gmail.com>

[realfun]

一开始我也是这么想的，但后来画张图分析过，这样倒推求解所有开局的方法不成立
只能在找出所有开局进行求解的时候耍点儿滑头，你可以看看这个代码：
http://www.fayaa.com/code/view/467/
它在一开始执行很慢，后来越来越快

我知道这个代码还有改进的空间，但是，够了，我要它来解题，而不是竞赛，我还要它能够被看懂，这就够了。

2008/10/25 Eric <xu.ma...@gmail.com>

[realfun]

另外，我提醒一下华容道的规则：连续移动一个棋子多步只算一步的

2008/11/4 Eric <xu.ma...@gmail.com>

[Eric]

On Nov 3, 6:30 pm, realfun <real...@gmail.com> wrote:
> 一开始我也是这么想的，但后来画张图分析过，这样倒推求解所有开局的方法不成立

为什么?

[realfun]

是求解开局，而不是推出开局
不同的开局会有不同的终局，这个之间的推导网络跟我一开始计划的复杂的多

2008/11/4 Eric <xu.ma...@gmail.com>

On Nov 3, 6:30 pm, realfun <real...@gmail.com> wrote:
> 一开始我也是这么想的，但后来画张图分析过，这样倒推求解所有开局的方法不成立

为什么?

[Eric]

On Nov 3, 6:32 pm, realfun <real...@gmail.com> wrote:
> 另外，我提醒一下华容道的规则：连续移动一个棋子多步只算一步的
>

这个我已经考虑了.

[Eric]

任何开局都能由某个终局走到，不是么？

我只要求到从终局到某个开局的最短路径， 不就是从开局到终局的最短路径么？

On Nov 3, 6:58 pm, realfun <real...@gmail.com> wrote:
> 是求解开局，而不是推出开局
> 不同的开局会有不同的终局，这个之间的推导网络跟我一开始计划的复杂的多
>

> 2008/11/4 Eric <xu.math...@gmail.com>

[realfun]

这个逻辑是不成立的，开局到终局 与 开局到指定终局 是不一定样的。你不会以为一个开局到所有终局（前面说过了，几百种）的路径都是一样的吧。

2008/11/4 Eric <xu.ma...@gmail.com>

[wangmao]

呵呵，最困难的3竖2横是138步^_^。最困难的2竖3横是135步。

[Eric]

realfun 你可能没有完全理解我的意思

你从所有的终局开始， 逐步的生成当前应该扩展的状态的领域状态，这些领域状态的步数就是现在的这些的步数+1

（在我的代码里面是用一个双缓冲做的， 参见double_buffer)

这是一个很自然的 frontier search 的过程， 我不明白这个过程有什么问题。

一个局势的确可以到很多种终局， 我在扩展的时候总是取最先到的那一个。

当然我的代码可能有一个小bug 我想你找的终局的数量是对的， 但是你dump 出来的结果 (log.txt ) 我完全不明白什么意思


On Nov 3, 11:20 pm, wangmao <lwm3...@gmail.com> wrote:
> 呵呵，最困难的3竖2横是138步^_^。最困难的2竖3横是135步。

[Eric]

realfun 兄

问题我找到了， 是你的生成所有终局的 python 程序漏掉了两个，

22112233333314401440

and

23322122332114401440

加入这两个开局之后， 我也是最长 138 步

下面是所有138步的组合， 可以到 http://www.fayaa.com/youxi/hrd/add/ 验证

DDDV
BBVV
BBVV
DHHV
HH

VDDD
VVBB
VVBB
VHH
HHD

VDDD
VVBB
VVBB
VHHD
HH

VDDD
VVBB
VVBB
VHHD
HH

DDDV
BBVV
BBVV
HHV
DHH

DDDV
BBVV
BBVV
DHHV
HH

整个 python 程序现在只要 5 秒， 而且最长的的确是138， 和你的观察一样。

另外我有90％的相信我的 262243 是正确的开局数目, 你的数目如何得到的？

[wangmao]

我的结果是去除镜像局面后正确的开奖数目是121285。难道俺错了？我可是从所有结束局面（没有去除镜像）倒推，然后保存的时候去掉镜像局面。我得到的138局面是

VDDD
VVBB
VVBB
VHHD
  HH

^__^

VDDD
VVBB
VVBB
VHH
HHD

^__^

VDDD
VVBB
VVBB
VHHD
HH 

^__^
刚好跟Eric没去掉镜像局面的是一样的。谁搞错了？

[realfun]

138无镜像确实是有三种，就是这三种。
不知道你的开局里面有没有包含终局，我的包含了终局？

2008/11/5 wangmao <lwm...@gmail.com>

[Eric]

1。 我的也包含了开局

2。 我的方法和你一样， 从结束局面开始倒推

3。 你镜像如何定义的， 绝对的左右镜像?

4。 你能否检查一下你的开局生成代码是否的确漏掉了我说的那两个开局？ 是否会漏掉更多？

[spellscroll]

>
> 整个 python 程序现在只要 5 秒， 而且最长的的确是138， 和你的观察一样。
>
> 另外我有90％的相信我的 262243 是正确的开局数目, 你的数目如何得到的？

大家报告程序执行时间的时候能不能顺带说一下机器配置, 以便参考.

[realfun]

1. 我是说包含了终局，也就是一步不用走的也被我计算在内
2. 镜像不是绝对镜像，只是按方块类型及排放左右径向
3. 我没有漏掉这两个开局，因为三个138步基本相同，我没有列出来而已
4. 像blog里面写的一样，得到138这个值以后我就失去了兴趣，你如果有兴趣的话可以对比一下程序运行的结果，很简单的，把所有的value打出来，排序，diff，找出不同的就行了。

2008/11/6 Eric <xu.ma...@gmail.com>

[realfun]

是求解所有还是只找最长？
如果是只找最长，5秒我信
如果是求解所有开局，还请亮出代码 :D

另外，我写程序检查过求解出来的所有开局(263977种，不含镜像132156种)，里面的value没有重复

强调一下：263977包含了终局，也就是一步也不用走的终局

2008/11/6 spellscroll <spell...@gmail.com>

>
> 整个 python 程序现在只要 5 秒， 而且最长的的确是138， 和你的观察一样。
>
> 另外我有90％的相信我的 262243 是正确的开局数目, 你的数目如何得到的？

大家报告程序执行时间的时候能不能顺带说一下机器配置, 以便参考.

[wangmao]

我所说的121285不包括终局不含镜像。在我1.9G的cpu上面使用python，我现在每秒钟搜索1w节点，目前我是找不到什么可以再优化的了，当然我个人水平比较有限。

[wang feng]

如果速度真的非常重要的话，不妨用c+＋写一遍；
wangmao wrote:
> 我所说的121285不包括终局不含镜像。在我1.9G的cpu上面使用python，我现在
> 每秒钟搜索1w节点，目前我是找不到什么可以再优化的了，当然我个人水平比较
> 有限。

[Eric]

我的代码就贴你的发芽上啦

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

你自己跑一下吧 我苹果上是13秒 双核P-D 是5秒

1. 我也包含了所有一步也不要走就能到达的.
2. 求解所有
3. 我说你漏掉"终局" 是从你生成所有终局的代码里面看出来的. 你的终局存成了一个字典, 你可以自己检验是否包含

2211
2233
3333
1440
1440

和

2332
2122
3321
1440
1440

我还是表达一个意思, 就是从终局扩展是可以做的, 而且很快. 就这个.

另外 @wangmao 你的算法可能和我不同而已, 你的不能优化不代表我的跑不到10秒之内.

[Eric]

realfun 兄

我检查了你比我多的， 比如这个

33333333133114401440

他对应的终局应该是

33333333133114401440

（用你的在线求解算的）

可是， 你的所有终局代码也不包含这个。

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

鉴于上次我算出141步而你是138步也是因为少了两个终局， 即

miss = ['22112233333314401440',
'23322122332114401440']

我觉得， 我用的生成终局的 layout 可能不完全， 是问题所在。 除此之外， 结果都是对的（注意到我的结果是你的结果的真子集， 也就是
说， 我是遗漏了什么才会比你少的， 而一开始我算出141步也是因为开局的遗漏）

我相信你的结果是完全的， 因为不同终局之间是联通的， 你只计算可达性, 所以所有的开局状态都能推导到。而我的结果是开局敏感的， 如果没有离一个
点最短的开局， 这个点我就算 close 了， 因此提早丢掉了一些。 （1734 个)

[realfun]

能说一下你是怎么做的吗？代码上看来，依然是错的。或许是我理解错误
你可以对比一下所有开局求解的结果

2008/11/6 Eric <xu.ma...@gmail.com>

[realfun]

因为我求解终局的时候并没有包含曹操右边为空的情况，因为这是镜像的，这不会对我的求解结果产生影响
如果你要倒推，至少需要遍历所有的终局，对每个终局，对走过的节点标上step，去最小的step

另外我要做的目标跟你不一样，不单单要知道所有开局的最短求解步数，还要知道这些最短路径怎么求解的（即求解步骤）
这也是从结局倒推很难做到的

这部分代码本来是为了将所有可求解开局的解导入数据库以替换在线求解程序的，不过后来有个朋友还说需要求解镜像（输赢不是曹出，而是左右、上下、中心镜像），这样我推出的求解路径还不够，而且这时已经感到乏味了，就没有做下去。

2008/11/7 Eric <xu.ma...@gmail.com>

[Eric]

我已经对比过了, 就是少掉了1734个呀. 我自己写了生成终局的代码之后, 就对了. 你漏掉了的终局, 就是我没能生成那 1734 个的原
因.

做法很简单, 从当前距离goal k 步的所有节点出发(这一步到goal 的距离都一样) 往下扩展一步, 如果扩展开的节点没有被计算过, 就插
入到一个扩展表中, 把步数记下.

然后从扩展表开始继续. 作为到goal K+1 步的所有结点.

就这样.

我应该从一开始就自己生成开局的. 折腾了大半天, 就是开局不完全, 而我的代码一定要有完全的开局才行.

>"如果你要倒推，至少需要遍历所有的终局，对每个终局，对走过的节点标上step，去最小的step "

我想你的理解偏差就出现在这个地方. 首先, 如果从所有终局扩展, 齐头并进, 先到的就是最小的 step. 这个是graph search,
道理很简单, 你想一下就知道了. 不需要标记然后选择最小的. 因为先到的就是最小的.

其次, 最短怎么求我不知道你熟不熟悉 A* search. 我已经说了很多遍了, "知道了最短距离求最短路径就是查表". 如果你不相信的话可
以看我的贴在发芽上的代码, 其实就是 A*.

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

从任何节点开始, 你想找到最短路径, 无非就是要看下一步怎么走. 你只需要检查这个节点通过一步移动可到达的所有节点B, 选择B中拥有最小的最短
距离的那个 b . 显然, 最短路径必然 就是沿着 b (如果有多个 b, 必然要沿着一个 b). 所以, 你就查表就行了, 对任意状态的邻
居, 查一下表. 选中下一个, 继续走. 这样, 不需要任何回溯, 就走到终局, 而且保证最优.

就7行核心代码. 会生成路径.

改一下这个程序, 跑完所有的华容道的例子, dump 出所有的路径, 也就4秒不到.

[realfun]

哇塞，多谢你的详细解释，确实如此
我最开始的时候想过用A*，被自己否定了，没想到这样就可以了

2008/11/7 Eric <xu.ma...@gmail.com>