#include<iostream>
#include<cstring>
#define DEST 46233    //The sequence num of "123456780",the destination
using namespace std;
struct Result{
	char status[10];
	short xPos;   //Current position of x
	char move[100];  //record the current searching record! Important
}eight[50000] = {0},*p = eight,*q = eight + 1;
char final[100] = {0};
static bool used[362881] = {false};    //to mark if the status has been searched
int count = 1;

int SequenceNum(const Result* m){
	int big[9] = {0},sum = 0;
	for(int i = 0;i < 8;++i){
		for(int j = i + 1;j < 9;++j){
			if(m->status[i] > m->status[j])++big[8-i];
		}
	}
	int fac = 1;
	for(int i = 1;i < 9;++i){
		sum += big[i] * fac;
		fac *= i + 1;
	}
	return sum;
}

int BFS(){
	int StatusNum,step,pos;
	char temp;
	while(true){
		pos = p->xPos;
		step = strlen(p->move);
		if(p->xPos > 2){
			strcpy(q->status,p->status);
			temp = q->status[pos];
			q->status[pos] = q->status[pos - 3];
			q->status[pos - 3] = temp;
			q->xPos = pos - 3;
			StatusNum = SequenceNum(q);
			if(used[StatusNum] == false){
				used[StatusNum] = true;
				strcpy(q->move,p->move);
				q->move[step] = 'u';
				if(StatusNum == DEST){
					strcpy(final,q->move);
					return step + 1;
				}
				if(q < eight + 49999)++q;
				else q = eight;
				++count;
			}
		}

		if(p->xPos < 6){
			strcpy(q->status,p->status);
			temp = q->status[pos];
			q->status[pos] = q->status[pos + 3];
			q->status[pos + 3] = temp;
			q->xPos = pos + 3;
			StatusNum = SequenceNum(q);
			if(used[StatusNum] == false){
				used[StatusNum] = true;
				strcpy(q->move,p->move);
				q->move[step] = 'd';
				if(StatusNum == DEST){
					strcpy(final,q->move);
					return step + 1;
				}
				if(q < eight + 49999)++q;
				else q = eight;
				++count;
			}
		}

		if(p->xPos%3 > 0){
			strcpy(q->status,p->status);
			temp = q->status[pos];
			q->status[pos] = q->status[pos - 1];
			q->status[pos - 1] = temp;
			q->xPos = pos - 1;
			StatusNum = SequenceNum(q);
			if(used[StatusNum] == false){
				used[StatusNum] = true;
				strcpy(q->move,p->move);
				q->move[step] = 'l';
				if(StatusNum == DEST){
					strcpy(final,q->move);
					return step + 1;
				}
				if(q < eight + 49999)++q;
				else q = eight;
				++count;
			}
		}

		if(p->xPos%3 < 2){
			strcpy(q->status,p->status);
			temp = q->status[pos];
			q->status[pos] = q->status[pos + 1];
			q->status[pos + 1] = temp;
			q->xPos = pos + 1;
			StatusNum = SequenceNum(q);
			if(used[StatusNum] == false){
				used[StatusNum] = true;
				strcpy(q->move,p->move);
				q->move[step] = 'r';
				if(StatusNum == DEST){
					strcpy(final,q->move);
					return step + 1;
				}
				if(q < eight + 49999)++q;
				else q = eight;
				++count;
			}
		}

		//Final: Process p
		if(p < eight + 49999)++p;
		else p = eight;
		--count;
	}
}

int main(){
	/* Get the original board */
	for(int i = 0;i < 9;++i){
		cin>>p->status[i];
		if(p->status[i] == 'x'){
			p->status[i] = '0';
			p->xPos = i;
		}
	}
	if(strcmp(p->status,"123456780") == 0){
		printf("0\n");
		return 0;
	}
	used[SequenceNum(p)] = true;
	memset(p->move,0,100*sizeof(char));
	/* Search and print result */
	BFS();
	printf("%s\n",final);
	return 0;
}

329ms