重点单词：

tile    n.瓦砖，地砖，瓦片，棋子

pack v.打包， 挤满，填封， 

configuration n.布局， 构造， 配置

出处：https://acs.jxnu.edu.cn/problem/POJ1077

Eight

 1000ms  65536K

描述：

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as: ”15“这个谜题已经存在了100多年；即使你不知道它的名字，你也见过它。它由15块滑动瓷砖组成，每一块上面都有一个从1到15的数字，所有这些瓷砖都装在一个4乘4的框架中，其中一块瓷砖缺失。让我们把丢失的瓷砖称为“x”；拼图的目的是排列瓷砖，使其按如下顺序排列：

 1  2  3  4 

 5  6  7  8 

 9 10 11 12 

13 14 15  x 

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle: 唯一合法的操作是将“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-> 

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively. 上一行中的字母表示在每一步中与“x”相邻的瓦砖与“x”交换的步骤；法定值分别为“r”、“l”、“u”和“d”，表示右、左、上和下。

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).并不是所有的谜题都能解决；1870年，一个名叫山姆·洛伊德的人因分发一个无法解决的谜题而出名，而

且这道谜题难倒了很多人。事实上，要把一个普通的谜题变成一个无法解决的谜题，你所要做的就是交换两个方块（当然不包括丢失的“x”方块）。

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement. 在这个问题中，您将编写一个程序来解决不太为人所知的8字谜，它由三乘三的方块组成

输入：

You will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle 你将收到8个拼图的配置说明。描述只是初始位置的瓷砖列表，行从上到下列出，瓷砖在一行内从左到右列出，其中瓷砖由数字1到8加上“x”表示。例如，这个谜题

 1  2  3 

 x  4  6 

 7  5  8 

is described by this list: 被描述成这一行：

 1 2 3 x 4 6 7 5 8 

输出：

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. 如果谜题没有解，你可以打印出“unsolvable”这个词，或者打印出一个完全由字母“r”、“l”、“u”和“d”组成的字符串，描述产生解的一系列动作。字符串不应包含空格，且从行首开始。

样例输入：

 2  3  4  1  5  x  7  6  8 

样例输出：

ullddrurdllurdruldr