1953_八数码

八数码游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3×3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上(up)、下(down)、左(left)、右(right)4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动。

例如，假设一个3×3矩阵的初始状态为：

8 0 3
2 1 4
7 6 5

目标状态为：

1 2 3
8 0 4
7 6 5

则一个合法的移动路径为：

8 0 3  d   8 1 3  l   8 1 3  u   0 1 3  r   1 0 3  d   1 2 3
2 1 4  =>  2 0 4  =>  0 2 4  =>  8 2 4  =>  8 2 4  =>  8 0 4
7 6 5      7 6 5      7 6 5      7 6 5      7 6 5      7 6 5

另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该状态无解。

请设计有效的算法找到从八数码的某初始状态到某目标状态的所有可能路径中的最短路径。

本题固定目标状态为 1 2 3 4 5 6 7 8 0，即

1 2 3
4 5 6
7 8 0

每组输入占一行，表示初始状态，由9个数字组成（x表示空格，1-8表示8个数字方块），数字之间用空格隔开。

如果本组输入数据有解，输出一行：最短路径的空格方块移动的动作序列，每个移动的动作：u表示向上移动，d表示向下移动，l表示向左移动，r表示向右移动；如果本组输入数据无解，输出 unsolvable 。

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

ullddrurdllurdruldr
r

2 3 4 1 5 x 7 6 8

表示的初始状态是：

2 3 4
1 5 x
7 6 8

21 2 3 4 5 6 7 x 8

表示的初始状态是：

1 2 3
4 5 6
7 x 8