拼图最优求解算法

Question

给定一个3×3的拼图，求解恢复拼图所用最少步数和每步的走法，比如：
拼图原始状态(.代表空格)：
1 2 3
4 5 6
7 8 .
现在的状态（输入）
1 2 3
4 8 5
7 6 .
等到答案：4， 走法：(2, 1) -> (1, 1) -> (1, 2) -> (2, 2)，括号中为每次移动的方块坐标。
感觉跟求迷宫最短路径问题差不多但貌似很不一样，想了一段时间还是没思路把代码写出来，请教高手，最好有代码或者伪代码，给思路也成。

Answer 1

先不用管最短的步聚.
这类问题用递归应该能做出来。
我的思路是，做一个3*3的数组s，s的每个元素又是一个二维数组
s[0][0]里放空格在(0,0)位置时，可能的移动，有两种：1.把（0，1）移过来，2.把（1，0）移过来，所以s[0][0]里放｛｛0，1｝，｛1，0｝｝以此类推。
把s数组做好后，可以用一个递归过程：step(i,j){
  if(和以前移动过程中的某一状态一样)｛
     return ;
   }
  if(恢复到原样）｛
        输出步骤。 
  ｝
  for(对s[i][j])中的每一种走法(x,y)）｛
     if((x,y)走法不是上一步过来的）{
         if(按(x,y)走法走后不会和以前存在栈中的状态相同)｛
            把(x,y) 记录在一个栈中。
            step(x,y);
          ｝
     ｝
  ｝
}
如果求移动次数最小的,普通的做法就是穷举，比较。

Answer 2

step(x,y)之前还应该保存一下前的状态。