带条件的优化矩阵算法征求

shiyiming

题目是一个平板游戏，一个正方形的方块分割成九个小方块，其中8个分别标有1-8的数字。还有一个空的方块可以和相邻的方块移动交换位置。
如图：9就代表空白的方块，他和6，8相邻所以可以将6这块方块的木板移动到原来空白的9这个位置上。
1 2 3
4 5 6
7 8 9
这里只有一个空白的方块可以和相邻直线的方块移动。
现在将问题转化成一个矩阵问题的形式，但是还是没有办法求解：
构造一个9行9列的大矩阵。列代表如上从左到右，从上到下的位置。123 456 789
行代表数字123456789的编码，如果编码5的数字在位置6上，那么第5行第6列数字就是1，其余不是1的都用0填充。问题转化成化一个矩阵为对角阵了。
如果要将打乱顺序的编号的方块比如：3 2 1化为上面的形状相当于把大矩阵化为对角的1矩阵。
但是由于相邻的条件限制它是依赖空 4 5 6木板的位置以及它相邻的木板找出一条可行的有序路径的。请各位大侠帮助                      7 8 9