魔方吧·中文魔方俱乐部

标题: 华容道的最远状态? [打印本页]

作者: 拼音佳佳 时间: 2008-7-5 23:39:07 标题: 华容道的最远状态?

对于华容道,可复原的最大状态是什么样的?
 
就是说,对于华容道游戏,摆出一个初始状态,该状态必须能够完成(曹操走出去),同时也是华容道的最远状态,要用最多的步数才能完成.
 
嗯,顺便提供一个滑块游戏,刚刚自己用易语言写的,只提供源代码

15数字板.e (48.38 KB, 下载次数: 60)

附件: 15数字板.e (2008-7-5 23:39:07, 48.38 KB) / 下载次数 60
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTk5OTF8NWZiMzdkYWV8MTcxNjc4OTYyNXwwfDA%3D

作者: magic_fish 时间: 2008-7-6 00:56:10

沙发啊～
最远状态不是曹操在最里面时么

作者: bbshanwei 时间: 2008-7-6 10:20:11

华容道的开局有很多但是好像多数的都可以用80多步解觉，不知道是不是他不存在最远态问题。

附件: hrd2.JPG (2008-7-6 10:20:11, 38.18 KB) / 下载次数 47
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjAwMjN8ZjRkZmVjOTl8MTcxNjc4OTYyNXwwfDA%3D

附件: hrd1.JPG (2008-7-6 10:20:11, 10.65 KB) / 下载次数 48
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjAwMjR8NjE1ZTEwZjd8MTcxNjc4OTYyNXwwfDA%3D

作者: bbshanwei 时间: 2008-7-6 10:20:30

呵呵，我只玩过横刀立马。

作者: 乌木 时间: 2008-7-6 10:42:57

“佳佳”是求答案还是已知答案？

终态时“曹操”当然紧挨着出口，而其余块的状态有没有什么规定呢？没规定的话，要不漏任一态。四个竖向的将官应保持区别吧；关公是横向的，没有重复块；四个小兵是否要有区别？转弯走算一步还是两步？

如果倒过来从同一终态开始走，记下所有的“一步态”，记下所有的“二步态”，…………。其间每一步是否都要消同态（如果会有的话）？对称的态算同态还是非同态？大概走到后来不再产生新态（即再走任一步时都是已出现过的态的同态），相应的步数和状态就算答案了。真不知这华容道的最远态是什么模样。
其实，还可以琢磨琢磨那通常给出的初态，能不能少于81步走出“曹操”，上次CCTV说中科院数学所正等着有关消息呢？

[ 本帖最后由乌木于 2009-2-23 20:50 编辑 ]

作者: bbshanwei 时间: 2008-7-6 14:47:38 标题: 回复 5# 的帖子

听说有少于81步的方法报于中科院是有奖励的。

作者: 拼音佳佳 时间: 2008-7-6 14:48:03

1.我没答案.昨晚玩易语言编程,想做华容道的,有点难度,就改成15数字滑块了.

2.只要曹操可以走出来,随便怎么摆放.五虎将不限横竖.

问题就是,如何摆放,才能让曹操用最多的步数走出来?

作者: 乌木 时间: 2008-7-6 15:25:14 标题: 回复 7# 的帖子

这是个数学难题吧？哪位会倒腾？

作者: kexin_xiao 时间: 2008-7-6 20:26:01

红舞3楼的图片不是原始状态吧？

作者: kexin_xiao 时间: 2008-7-6 20:26:27

LZ出的题目属于数学问题了，我不会，等着一起学习

作者: ggglgq 时间: 2008-7-7 16:55:31

         这个问题相对 21 世纪来说，好象不难了！请大家参考：         <A href="http://bbs.mf8-china.com/viewthread.php?tid=2416">游戏华容道的历史与解法 </A>         <A href="http://bbs.mf8-china.com/viewthread.php?tid=2416">http://bbs.mf8-china.com/viewthread.php?tid=2416</A>       

[ 本帖最后由 ggglgq 于 2008-7-7 16:56 编辑 ]

作者: yzl-34 时间: 2008-7-7 17:40:06

华容道？貌似很难的样子

作者: yjw44 时间: 2008-7-7 18:02:05

没玩过这个

网上有下载吧?下一个玩玩...

作者: yinhaitang 时间: 2008-7-14 16:02:19

这是否算一横式的最远状态

附件: hrd1.gif (2008-7-14 16:02:19, 2.63 KB) / 下载次数 25
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjA2NzR8ZmIyZTk0N2J8MTcxNjc4OTYyNXwwfDA%3D

作者: 华容道 时间: 2009-2-15 21:44:09

无标题.jpg

最远状态为上图所示的“峰回路转”局，最少要138步才能将曹操移出！

附件: 无标题.jpg (2009-2-15 21:44:09, 3.44 KB) / 下载次数 34
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzg4MTZ8ODE3ZDFmODd8MTcxNjc4OTYyNXwwfDA%3D

作者: 华容道 时间: 2009-2-15 21:48:35

一横类最难布局名为“欲罢不能”，最少需93步！
无标题.jpg

附件: 无标题.jpg (2009-2-15 21:48:35, 3.55 KB) / 下载次数 34
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzg4MTd8ZTMyMWZiMmR8MTcxNjc4OTYyNXwwfDA%3D

作者: unknownzone 时间: 2009-2-15 21:52:33

易语言是啥？源文件居然用文本编辑器还打不开。。。

作者: lulijie 时间: 2009-2-19 21:16:21

本图，193步

--------------------------------
哈哈，出错了。
不好意思

[ 本帖最后由 lulijie 于 2009-2-19 21:26 编辑 ]

附件: a.jpg (2009-2-19 21:16:21, 8.84 KB) / 下载次数 28
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MzkxNjN8YWRiY2VlMjN8MTcxNjc4OTYyNXwwfDA%3D

作者: flwb 时间: 2009-2-20 21:53:39

三楼您好,您的那个图是游戏截图吗?那个版本在哪里有下?
能传个附件上来吗?

[ 本帖最后由 flwb 于 2009-2-20 21:55 编辑 ]

作者: lulijie 时间: 2009-2-22 18:05:37

华容道可研究的东西很多：
4*5 的格子里，放入2*2的方块1个，1*1的方块4个，1*2的方块5个。
1. 若随机摆放，一共有多少种放法？其中有解的有多少种？
2. 若两种摆放状态，可通过移动相互转化，那么称它们为同族，那么一共有多少种不同的族？不同的族间不能通过移动转化。
3. 1*2的方块一个横放，另4个竖放（比如横刀立马），这种放法是否只有一个族，若不是，一种有多少个族？
4. 每一族内有最远状态，它成功移出的最少步数是最大的。每一个族都有个最远状态，其中有个族，它的最远状态是所有中最远的，这个族是什么？最远状态（步数）是多少？

作者: lulijie 时间: 2009-2-22 18:56:54

本图，178步

附件: hrd.jpg (2009-2-22 18:56:54, 9.58 KB) / 下载次数 29
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk1NDJ8MmYwN2IxY2J8MTcxNjc4OTYyNXwwfDA%3D

作者: lulijie 时间: 2009-2-22 19:32:30

a. 16楼的欲罢不能 126步
欲罢不能.JPG

b. 最常见的横刀立马 116步
横刀立马.JPG

c. 14楼的 116步
14#.JPG

a、b、c属于同族，最远状态126步，a是其中的一种，总共有4种。
---------------------------------------------------------------------
d. 3楼的兵临曹营，49步
兵临曹营.JPG

该族中最远状态91步，一共4种，以下是其中之一
兵临曹营2.JPG

附件: 欲罢不能.JPG (2009-2-22 19:32:30, 8.42 KB) / 下载次数 29
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk1NDR8ODFmYmFhMDB8MTcxNjc4OTYyNXwwfDA%3D

附件: 横刀立马.JPG (2009-2-22 19:32:30, 6.88 KB) / 下载次数 31
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk1NDV8N2U2Njc2MjN8MTcxNjc4OTYyNXwwfDA%3D

附件: 14#.JPG (2009-2-22 19:32:30, 8.14 KB) / 下载次数 31
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk1NDZ8OGQwNTM1MjN8MTcxNjc4OTYyNXwwfDA%3D

附件: 兵临曹营.JPG (2009-2-22 19:32:30, 6.96 KB) / 下载次数 25
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk1NDd8ODYyYjhhODV8MTcxNjc4OTYyNXwwfDA%3D

附件: 兵临曹营2.JPG (2009-2-22 19:32:30, 7.78 KB) / 下载次数 30
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk1NDh8NzNiNGFhNjB8MTcxNjc4OTYyNXwwfDA%3D

作者: 华容道 时间: 2009-2-23 09:40:01

横刀立马的最优解为81步，你所提供的那个三横类布局的最优解为135步！

作者: 华容道 时间: 2009-2-23 09:42:42

若是有兴趣，可以去游戏发芽网，那里有网上最全的华容道游戏http://www.fayaa.com/youxi/hrd/#hrd-layouts

作者: lulijie 时间: 2009-2-23 19:10:55

他们的最优解把一个子连续移动的所有步数算作一步，不符合实际情况，不应该采取这种算法。

作者: lulijie 时间: 2009-2-23 19:12:49

我的解法绝对正确，不可能还有比它步数更少的解法了。

作者: 华容道 时间: 2009-2-23 19:16:15

哦，“步数”的理解不一样。

作者: lulijie 时间: 2009-2-23 20:07:53

15楼的峰回路转179步，该家族中最远步数就是179步，共6种状态。
峰回路转6.JPG

目前我所知的最多步数就是它了。
不知还有没有更多步数的。

附件: 峰回路转6.JPG (2009-2-23 20:07:53, 22.42 KB) / 下载次数 46
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk2NDZ8MjUzZjNkNjR8MTcxNjc4OTYyNXwwfDA%3D

作者: 华容道 时间: 2009-2-26 21:01:01

有人用计算机证明了峰回路转是“曹出”玩法的最远状态。

作者: 好梦游 时间: 2009-3-2 21:21:46

应该是初始状态吧。。。

作者: xdgtzsyyj 时间: 2009-6-13 11:37:43

最远饿好像是120步左右

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)