解“华容道”

〇〇 · 发表于 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

这些天终于看明白一点了

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

[游戏] 解“华容道”

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