出个稍微有点难度的问题――重排九宫

问题：在3×3的方格棋盘上放置分别标有数字1～8的8个棋子，初始状态为左图，目标状态为右图：

2    8    3                1    2    3
1          4                8           4
7    6    5                7    6    5

横竖的表格线这里就不画了。可使用的操作有：
                空格左、右、上、下移动。（即只允许位于空格左、右、上、下的临近棋子移入空格。）

要求：编写程序寻找从初始状态到目标状态的路径。
----------------解决方案--------------------------------------------------------
printf("8 2 1 8");

每个数字表示哪一个数字移入空格
----------------解决方案--------------------------------------------------------
啊……这个问题我的《计算机算法(C++版)》里面有啊……
----------------解决方案--------------------------------------------------------
好像很简单！！！支持楼主，继续贴啊！！！
----------------解决方案--------------------------------------------------------
^_^, 没有各位想象的那么简单
1. 我给出的只是一个例子, 初始矩阵需要由用户设置或者随机生成;
2. 要让程序去计算每一步将哪个数移入空格, 而不是让你的大脑去计算.
----------------解决方案--------------------------------------------------------
经典算法A*，不过BFS效率也不差多少
----------------解决方案--------------------------------------------------------
是有难度..顶一下
----------------解决方案--------------------------------------------------------
A*算法和宽度优先，只不过是众多有效算法中的两种，:-)
有很多很多种不同的解法
----------------解决方案--------------------------------------------------------
那你随便列举“很多很多”中的两种吧。
----------------解决方案--------------------------------------------------------
与或树、遗传算法、动态规划
甚至分冶、贪心也行
----------------解决方案--------------------------------------------------------