《算法竞赛宝典》基础算法艺术(公开课程)

【题目描述】15数码问题（Puzzle15.cpp/c/pas）uva 10181

“呵呵，你真以为这世上有无所不能的神？实话告诉你，很久以前，宇宙中的几大黑暗势力就在你们星球上通过创立各种宗派收罗信众，并暗中挑动了不计其数的宗派战争以收割你们人类的生命力（命源）。所谓的创世神传说，也不过是我们在远古时代就布局抛给你们的诱饵而已。当然我们比他们要仁慈，像他们那种通过战争来收割生命力（命源）的低级手段就像杀鸡取卵一样愚蠢，但再愚蠢，也比不过你们彼此残杀数十万年而不醒悟的愚蠢。看到这道15谜问题了吗，当你解开它，你就会知道我们的来历了。”所谓的守护者在吸收了赢来的魔法石上足够的能量后，对修罗王说。　

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

【输入格式】

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

【输出格式】

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

【输入样例】

 2

 2 3 4 0

 1 5 7 8

 9 6 10 12

 13 14 11 15

 13 1 2 4

 5 0 3 7

 9 6 10 12

 15 8 11 14

【输出样例】

LLLDRDRDR

This puzzle is not solvable.