今天面试题目,大家帮忙看看

今天去一家公司笔试,最后一道大题没做,抄了回来,大家帮忙看看.

有5×5的方格棋盘,棋盘上放着25颗不同的棋子,分别用英文字母A~X表示,棋盘上有一个方格空着,用空格表示.
游戏的的每一步是将空格上、下、左、右等方位的棋子移入空格，这4钟操作分别用1、2、3、4表示，
如果给出的棋盘的初始状态和一定顺序的有限操作序列，就可以得到唯一的目标状态。例如：

T	E	G	S	J
X	D	O	K	I
M		V	L	N
W	F	A	B	E
U	Q	H	C	F

经过操作序列"144223"移动后，得到如下状态：

T	R	G	S	J
X	O	K	L	I
M	D	V	B	N
V	P		A	E
U	Q	H	C	F

但是，原来正确的操作序列的顺序被打乱了，初态按照被打乱的操作序列并不能得到终态（仅仅是顺序上被打乱，各类型操作总数不变）。
已知棋盘的初态、棋盘的终态和被打乱后的操作序列（操作序列长度L<=50），要求计算和输出原来正确的操作序列，若无解，则输出0。（要求最优性能）

发现一个很严重的问题，不碰到墙壁的话，操作顺序被打乱也不影响终态。所以找出正确的操作序列只不过是随便找出一个不钻墙的操作系列而已。

算法啊，相当有难度。。。。 :o