“15数码”游戏已经存在超过100年了。它是由15个可滑动的方块构成，每个方块上有数字，数字是1到15，并且放在一个4*4的宫格中，这里我们把缺少的那个方块称为x,拼图的目的就是滑动方块最终以下图的顺序排列：

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

在移动方块的过程中，只能将x与其同行或同列的相邻的方块交换，举个例题，下图示例了一个解题过程：

图中的字母表示每一步x的移动规则，每次移动时x只能够向‘上’‘下’‘左’‘右’四个方向移动，分别用字母‘u’‘d’‘l’‘r’表示。
本题要求你编写一个程序来解决一个8数码游戏,8数码游戏同15数码规则一样，只是数字是1到8另外有一个字母x，放在一个3*3的宫格中。
这里我们用“1 2 3 x 4 6 7 5 8”来描述如下的一个8数码题，即按照从左到右从上到下的顺序列出方块的数字。

1 2 3
x 4 6
7 5 8

输入包含多组数据，每组数据一行，描述一个8数码题

对于每个8数码题，如果有解则输出整个解题过程用字母‘u’‘d’‘l’‘r’表示，字母间无空格；如果无解输出“unsolvable”

2 3 4 1 5 x 7 6 8

状态空间搜索 level8