解“华容道”

〇〇 · 发表于 2009-11-11 19:53:11

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

解“华容道” 3*3的格子，里面随机放上数字1~8，每个格子放1个数，1个格是空的，每次只能移1个数字到空格，不能出界（我手机里有这个游戏）用最少移动步骤实现 1 2 3 4 5 6 7 8 问题可推广到n*n

056254628 · 发表于 2009-11-11 20:37:51

3*3，只有一半有解。最远的状态为31步，只有2个， 647 85 321 和 867 254 3 1 右下角为空格的最远状态为30步，一共45种，如 347 682 51

〇〇 · 发表于 2009-11-12 15:59:47

过程是怎么样的

sheng_jianguo · 发表于 2009-11-13 10:09:19

我分析过下面图中的移动方法: 九方格.jpg

据说移动次数最少的世界记录为30步，方法有10种。通过自编的程序计算，证实了这个结论是正确的。下面是我的计算结果，其中数字表示移动棋子的编号： 1）347852178521785643856436421458 2）347852174374863865214786521478 3）345875134651328713246532487456 4）345215764357682176843568421456 5）345215435478214786386214758658 6）147852478638652471861741521478 7）145875365341653412874128741256 8）143142587316312587125465487456 9）125874852831825743163125741258 10)125874312587431631526528741256

raa · 发表于 2009-11-13 12:00:51

编的过程呢？

〇〇 · 发表于 2009-11-13 12:26:03

记录学习

sheng_jianguo · 发表于 2009-11-13 13:02:27

本帖最后由 sheng_jianguo 于 2009-11-13 13:10 编辑 接4# 当时（好几年前）觉得此问题很有意思，就简单编了个程序进行计算，也没考虑编程的技巧性，基本思路就是找出≤30步的所有可能棋局，看是否有和要求棋局相同。当然n较大时，这个方法是行不通的。这里有很多编程高手，他们会有好的求解方法，在这里学习了。

mathe · 发表于 2009-11-13 13:22:59

这个问题通常我们称为九宫格或八数码问题，是个很古老的问题了。对于3*3情况，现在的计算机穷举完全不是问题（甚至应该可以扩大到4*4的规模）。但是对于更加大的规模，求最优解几乎不可能。而如果仅仅求一个解，或者判断是否可解，都是很简单的事。 google一把应该可以找到很多解答。本论坛里面发现kon3155发过一个参考程序: http://bbs.emath.ac.cn/viewthrea ... fromuid=20#pid16617

〇〇 · 发表于 2009-11-17 10:37:17

这些天终于看明白一点了

账号		自动登录	找回密码
密码			欢迎注册

[游戏] 解“华容道”

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。