说明

这是一道Special Judge题，Sepcial Judge Module By stong9070

题目描述

十五数码问题是由$15$块滑动的方块构成的，在每一块上都有一个$1～15$的数字，所有方块都是一个$4×4$的排列，其中一块方块丢失，称之为“$x$”。拼图的目的是排列方块，使其按以下顺序排列：

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  x

其中唯一合法的操作是将“$x$”与相邻的方块之一交换。下面的移动序列解决了一个稍微混乱的拼图：

 1  2  3  4     1  2  3  4     1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8     5  6  7  8     5  6  7  8
 9  x 10 12     9 10  x 12     9 10 11 12     9 10 11 12
13 14 11 15    13 14 11 15    13 14  x 15    13 14 15  x
            r->            d->            r->

上一行中的字母表示在每个步骤中“$x$”方块的哪个邻居与“$x$”交换；

合法值分别为“$r$”“$l$”“$u$”和“$d$”，表示右、左、上和下。

在这个问题中，编写一个程序来解决八数码问题，它由$3×3$的排列组成。

输入格式

输入包含多个测试用例，但保证测试用例数 $T≤220$

每行输入一组测试用例，描述是初始位置的方块列表，从上到下列出行，在一行中从左到右列出方块，其中的方块由数字$1～8$加上“x”表示。例如以下拼图

1 2 3
x 4 6
7 5 8

由以下列表描述：

1 2 3 x 4 6 7 5 8

输出描述

如果没有答案，则输出“unsolvable”，否则输出由字母“$r$”“$l$”“$u$”和“$d$”组成的字符串，描述产生答案的一系列移动。字符串不应包含空格，并从行首开始。

样例

2 3 4 1 5 x 7 6 8

ullddrurdllurdruld

x 1 2 3 4 8 7 6 5
x 5 4 2 6 3 7 1 8 
8 3 5 4 7 x 6 2 1 
7 5 x 3 4 6 1 2 8 
1 3 8 2 7 6 x 5 4 
6 8 x 3 4 2 1 5 7

drdrululdrdruulldrruldlurrdluldrrd
ddrrulurdluldrrdlurulddrulurdllurrddllurdlurulddrr
ulldrdluurdrdlurulldruldrurddllurdruldlurrdluldrr
ldlurddruuldrdlluurddlurulddrr
urdlurdruuldrdluldrruldlurrd
dlulddruulddrrulldrruldlurdlurruldrdluldruulddrulurddr

1 x 4 3 2 5 6 7 8
1 3 8 2 7 6 x 5 4

unsolvable
urdlurdruuldrdluldrruldlurrd

说明

出于学习的目的，我们将第一、二个数据点设置为：$T≤5$。

普通BFS复杂度分析：共有 $9!=326880$ 种情况，可以做到 $log=20$ 判重，有 $T$ 组数据

整体复杂度为： $9!*20 * T=6e6*T$，也就是说普通BFS只能接受 $T≤10$ 的数量级。

来源

• HDU1043
• POJ1077
• South Central USA 1998