209017 - 15数码问题

15数码问题是在一个4×4的方格棋盘上，将数字1，2，3，…，14，15以任意顺序置入棋盘的各个方格中，空出一格，通过有限次移动，把一个给定的初始状态变成目标状态，如图9.25所示。移动规则是：每次只能在空格周围的四个数字中任选一个移入空格。可以证明的是，一共16！的初始状态中，有一半是不可能移成目标状态的。 图9.25

第一行为一个整数N，表示有N组数据，随后是N组4×4的棋盘初始状态描述。

若在50步内不能完成，输出“This puzzle is not solvable.”，否则输出步数如样例所示。其中R，L，U和D分别代表左，右，上和下。