解“华容道”
解“华容道”3*3的格子，里面随机放上数字1~8，每个格子放1个数，1个格是空的，每次只能移1个数字到空格，不能出界（我手机里有这个游戏）
用最少移动步骤实现
1 2 3
4 5 6
7 8
问题可推广到n*n 3*3，只有一半有解。
最远的状态为31步，只有2个，
647
85
321
和
867
254
3 1
右下角为空格的最远状态为30步，一共45种，如
347
682
51 过程是怎么样的 我分析过下面图中的移动方法:
据说移动次数最少的世界记录为30步，方法有10种。通过自编的程序计算，证实了这个结论是正确的。下面是我的计算结果，其中数字表示移动棋子的编号：
1）347852178521785643856436421458
2）347852174374863865214786521478
3）345875134651328713246532487456
4）345215764357682176843568421456
5）345215435478214786386214758658
6）147852478638652471861741521478
7）145875365341653412874128741256
8）143142587316312587125465487456
9）125874852831825743163125741258
10)125874312587431631526528741256 编的过程呢？ 记录学习 本帖最后由 sheng_jianguo 于 2009-11-13 13:10 编辑
接4#
当时（好几年前）觉得此问题很有意思，就简单编了个程序进行计算，也没考虑编程的技巧性，基本思路就是找出≤30步的所有可能棋局，看是否有和要求棋局相同。当然n较大时，这个方法是行不通的。
这里有很多编程高手，他们会有好的求解方法，在这里学习了。 这个问题通常我们称为九宫格或八数码问题，是个很古老的问题了。
对于3*3情况，现在的计算机穷举完全不是问题（甚至应该可以扩大到4*4的规模）。
但是对于更加大的规模，求最优解几乎不可能。而如果仅仅求一个解，或者判断是否可解，都是很简单的事。
google一把应该可以找到很多解答。
本论坛里面发现kon3155发过一个参考程序:
http://bbs.emath.ac.cn/viewthread.php?tid=1260&page=2&fromuid=20#pid16617 这些天终于看明白一点了
页:
[1]