问题 3091 --15数码问题

3091: 15数码问题

题目描述

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

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

输入

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

输出

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

样例输入输出

输入#1 复制
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
输出#1 复制
LLLDRDRDR
This puzzle is not solvable.

提示

序号 标题 作者 发表时间 费用 订购数 操作