#include <iostream>#include <cstdio>#include <math.h>#include <time.h>#include <algorithm>#include <string.h>using namespace std;const int maxn = 362885;struct NType{int statue[10];int place;int pre;int step;char opt;};struct HType{int pos;int val;};bool cmp (struct HType a, struct HType b){return a.val > b.val;}int dirx[] = {-1, 0, 0, 1};int diry[] = {0, -1, 1, 0};int poschg[] = {-3, -1, 1, 3};char op[] = "ulrd";int move (NType s, NType &e, int optNum, int pre){int i, j, tr, tc, tp;i = s.place / 3;j = s.place % 3;tr = i + dirx[optNum];tc = j + diry[optNum];if (tr >= 0 && tr < 3 && tc >= 0 && tc < 3){e = s;tp = e.place;e.place += poschg[optNum];e.statue[tp] = e.statue[e.place];e.statue[e.place] = 0;e.pre = pre;e.opt = op[optNum];e.step++;return 1;}return 0;}int dist (int * statue, int place){int ret = 0;statue[place] = 9;for (int i = 0, j; i < 9; i++){j = statue[i] - 1;ret += abs(i / 3 - j / 3) + abs(i % 3 - j % 3);}statue[place] = 0;return ret;}int fact[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};int cantor (int * statue){int ans = 0, num = 0, n = 8;int flag[10] = {0};for (int i = 0; i < 9; i++){int up = statue[i];flag[up] = 1;num = 0;for (int k = 0; k < up; k++) if (!flag[k]) num++;ans += num * fact[n];n--;}return ans;}int sst[10], est[10], splace, eplace, vis[maxn];NType queue[maxn];HType heap[maxn];int head, rear, hp;void output (int pos){if (pos == 0) return;output(queue[pos].pre);putchar(queue[pos].opt);}void AStar (){int rpre, pos = -1, epre, spre;head = rear = hp = 0;memcpy(queue[rear].statue, sst, sizeof(sst));spre = cantor(sst);epre = cantor(est);queue[rear].place = splace;queue[rear].pre = -1;queue[rear].step = 0;vis[spre] = 1;rear++;heap[hp].pos = 0;heap[hp].val = 10 * dist(queue[head].statue, splace); hp++;if (spre == epre) {pos = 0; goto lable;}while (hp > 0){head = heap[0].pos;pop_heap(heap, heap + hp, cmp);hp--;for (int i = 0; i < 4; i++){if (move(queue[head], queue[rear], i, head)){rpre = cantor(queue[rear].statue);if (vis[rpre]) continue;vis[rpre] = 1;heap[hp].pos = rear;heap[hp].val = 10 * dist(queue[rear].statue, queue[rear].place) + queue[rear].step;push_heap(heap, heap + (++hp), cmp);rear++;if (epre == rpre) {pos = rear - 1; goto lable;}}}}lable:output(pos);}bool isSolveable (int *statue){int arr[10], n = 0, num = 0;for (int i = 0; i < 9; i++){if (statue[i] != 0) arr[++n] = statue[i];}for (int i = 1; i <= 8; i++){for (int j = i + 1; j <= 8; j++){if (arr[i] > arr[j]) num++;}}if (num & 0x1) return false;return true;}int main (){char c;for (int i = 0; i < 8; i++) est[i] = i + 1;est[8] = 0; eplace = 8;while (1){for (int i = 0; i < 9; i++){if (scanf(" %c", &c) == EOF) {return 0;}if (c == 'x'){sst[i] = 0;splace = i;}else sst[i] = c - '0';}memset(vis, 0, sizeof(vis));if (isSolveable(sst)){AStar();putchar('n');}else printf("unsolvablen");}return 0;}
