1 /*
2 zju 1217
3 HDu 1043
4 ymc 2008/5/28
5 解题思路：
6 把x看作0，则每种状态对应012345678的一个排列。终止状态为123456780。
7 012345678总共有有9！种排列，按照字典顺序给所有的排列排序，012345678在最前面，876543210在最后面。
8 ptonum() 求出一个排列的序号
9 numtop() 给出给定序号的排列
10 从开始状态到终止状态BFS搜索 TLE
11 反过来思BFS终止状态到所有状态的最短路径，对每次查询只要生成输出就可以
12 */
13 #include <iostream>
14 #include <queue>
15 using namespace std;
16 const int Max=362880; //9!
17 const int N=9;
18 int f[N];
19 int map[N]={1,2,3,4,5,6,7,8,0};
20 int Trans[Max][4]; //记录各种状态间的转移，每种状态最多转移到四种状态。上下左右
21 char Transop[Max][4];//各种状态转移的操作
22 int start,end;
23 struct Operator
24 {
25 int next;
26 char op;
27 };
28 Operator OP[Max]; //其实状态到终止状态的最短路径以及操作（逆序）
29
30 int ptonum(int a[]) //012345678的所有排列按照字典顺序排列，任意给出一个排列，计算在排列中的序号。
31 {
32 bool used[N];
33 memset(used,0,sizeof(used));
34 int ans=0;
35 int num;
36 for(int i=0;i<N;i++)
37 {
38 num=0;
39 for(int j=0;j<a[i];j++)
40 {
41 if(!used[j])
42 num++;
43 }
44 ans+=num*f[N-1-i];
45 used[a[i]]=true;
46 }
47 return ans;
48 }
49 void numtop(int a[],int num)//求给定序号的排列
50 {
51 bool used[N];
52 memset(used,0,sizeof(used));
53 int k;
54 for(int i=0;i<N;i++)
55 {
56 if(i!=N-1)
57 {
58 k=num/f[N-1-i];
59 num=num%f[N-1-i];
60 }
61 else
62 k=num;
63 int id=0;
64 int j;
65 for(j=0;j<N;j++)
66 {
67 if(!used[j])
68 {
69 if(id==k)
70 break;
71 id++;
72 }
73 }
74 a[i]=j;
75 used[j]=true;
76 }
77 }
78 void init() //主要求出所有的状态转移，以及对应的操作。
79 {
80 f[0]=0;
81 f[1]=1;
82 for(int i=2;i<N;i++)
83 f[i]=f[i-1]*i;
84 end=ptonum(map);
85 memset(Transop,'d',sizeof(Transop));
86 int num,tmp,k,v;
87 int b[N];
88 for(int u=0;u<Max;u++)
89 {
90 num=0;
91 numtop(b,u);
92 for(k=0;k<N;k++)
93 if(b[k]==0) break;
94 if(k>=3) //x上移
95 {
96 tmp=b[k];b[k]=b[k-3];b[k-3]=tmp;
97 v=ptonum(b);
98 Trans[u][num]=v;
99 Transop[u][num]='d';
100 num++;
101 tmp=b[k];b[k]=b[k-3];b[k-3]=tmp;
102 }
103 if(k<6) //x下移
104 {
105 tmp=b[k];b[k]=b[k+3];b[k+3]=tmp;
106 v=ptonum(b);
107 Trans[u][num]=v;
108 Transop[u][num]='u';
109 num++;
110 tmp=b[k];b[k]=b[k+3];b[k+3]=tmp;
111 }
112 if(k%3!=0) //x左移
113 {
114 tmp=b[k];b[k]=b[k-1];b[k-1]=tmp;
115 v=ptonum(b);
116 Trans[u][num]=v;
117 Transop[u][num]='r';
118 num++;
119 tmp=b[k];b[k]=b[k-1];b[k-1]=tmp;
120 }
121 if(k%3!=2) //x右移
122 {
123 tmp=b[k];b[k]=b[k+1];b[k+1]=tmp;
124 v=ptonum(b);
125 Trans[u][num]=v;
126 Transop[u][num]='l';
127 num++;
128 tmp=b[k];b[k]=b[k+1];b[k+1]=tmp;
129 }
130
131 }
132 }
133 int Reverse(int a[N])
134 {
135 int sum=0;
136 int b[N];
137 memset(b,0,sizeof(b));
138 for(int i=0;i<N;i++)
139 {
140 for(int j=0;j<i;j++)
141 if(a[j]>a[i])
142 b[a[i]]++;
143 sum+=b[a[i]];
144 }
145 return sum-b[0];
146 }
147 void PreBFS()
148 {
149 bool used[Max];
150 memset(used,0,sizeof(used));
151 // start=ptonum(map);
152 queue<int> q;
153 q.push(end);
154 used[end]=true;
155 int u,v;
156 while(!q.empty())
157 {
158 u=q.front();
159 for(int i=0;Trans[u][i]!=0&&i<4;i++)
160 {
161 v=Trans[u][i];
162 if(!used[v])
163 {
164 used[v]=true;
165 OP[v].next=u;
166 OP[v].op=Transop[u][i];
167 q.push(v);
168 }
169 }
170 q.pop();
171 }
172 }
173 void output()
174 {
175 int st=start;
176 while(st!=end)
177 {
178 cout<<OP[st].op;
179 st=OP[st].next;
180 }
181 cout<<endl;
182 }
183
184 int main()
185 {
186 init();
187 PreBFS();
188 char ch;
189 while(cin>>ch)
190 {
191 if(ch!='x')
192 map[0]=ch-'0';
193 else
194 map[0]=0;
195 for(int i=1;i<N;i++)
196 {
197 cin>>ch;
198 if(ch!='x')
199 map[i]=ch-'0';
200 else
201 map[i]=0;
202 }
203 int tmp=Reverse(map);
204 if(tmp%2!=0)
205 {
206 cout<<"unsolvable\n";
207 continue;
208 }
209 start=ptonum(map);
210 output();
211 }
212 }