#include<stdio.h>
#include<conio.h>

int n,m;
typedef struct Node
{
	char matrix[10];
	char operate;
	char extend;
	int  father;
}Node;
char start[10]={"83426517 "};
char end[10]={"1238 4765"};
Node base[4000];
int result[100];
int match()
{
	int i;
	for(i=0;i<9;i++)
	{
		if(base[n-1].matrix[i]!=end[i])
		{
			return 0;
		}
	}
	return 1;
}

void show()
{
	int i=1;
	while(m>=0)
	{
		int mm=result[m];
		clrscr();
		printf("\n\n\n      Burgess Lee\t\tStep %d",i);
		printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);
		printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);
		printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);
		sleep(1);
		m--;
		i++;
	}
	sleep(5);
}

void leave()
{
	n--;
	while(base[n].father!=-1)
	{
		result[m]=n;
		m++;
		n=base[n].father;
	}
	result[m]=0;
	result[m+1]='\0';
	show();
	clrscr();
	printf("\n\n\n\n\n\n\n\n\n\t\t\t\tThe End\n\n\n\n\n\n\n\n\n\n");
	getch();
	exit(0);
}

int left(int x)
{
	int i,j;
	char ch;
	for(i=0;i<9;i++)
	{
		if(base[x].matrix[i]==' ')
			break;
	}
	if(i==0||i==3||i==6||i==9)
	{
		return 0;
	}
	for(j=0;j<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}
	ch=base[n].matrix[i-1];
	base[n].matrix[i-1]=base[n].matrix[i];
	base[n].matrix[i]=ch;
	base[n].operate='R';
	base[n].extend='Y';
	base[n].father=x;
	base[x].extend='N';
	n++;
	if(match())
		leave();
	return 1;
}

int right(int x)
{
	int i,j;
	char ch;
	for(i=0;i<9;i++)
	{
		if(base[x].matrix[i]==' ')
			break;
	}
	if(i==2||i==5||i==8||i==9)
	{
		return 0;
	}
	for(j=0;j<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}
	ch=base[n].matrix[i+1];
	base[n].matrix[i+1]=base[n].matrix[i];
	base[n].matrix[i]=ch;
	base[n].operate='L';
	base[n].extend='Y';
	base[n].father=x;
	base[x].extend='N';
	n++;
	if(match())
		leave();
	return 1;
}

int up(int x)
{
	int i,j;
	char ch;
	for(i=0;i<9;i++)
	{
		if(base[x].matrix[i]==' ')
			break;
	}
	if(i==0||i==1||i==2||i==9)
	{
		return 0;
	}
	for(j=0;j<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}
	ch=base[n].matrix[i-3];
	base[n].matrix[i-3]=base[n].matrix[i];
	base[n].matrix[i]=ch;
	base[n].operate='D';
	base[n].extend='Y';
	base[n].father=x;
	base[x].extend='N';
	n++;
	if(match())
		leave();
	return 1;
}

int down(int x)
{
	int i,j;
	char ch;
	for(i=0;i<9;i++)
	{
		if(base[x].matrix[i]==' ')
			break;
	}
	if(i==6||i==7||i==8||i==9)
	{
		return 0;
	}
	for(j=0;j<9;j++)
	{
		base[n].matrix[j]=base[x].matrix[j];
	}
	ch=base[n].matrix[i+3];
	base[n].matrix[i+3]=base[n].matrix[i];
	base[n].matrix[i]=ch;
	base[n].operate='U';
	base[n].extend='Y';
	base[n].father=x;
	base[x].extend='N';
	n++;
	if(match())
		leave();
	return 1;
}

main()
{
	int i;
	n=1;
	textcolor(LIGHTGREEN);
	clrscr();
	for(i=0;i<9;i++)
	{
		base[0].matrix[i]=start[i];
	}
	base[0].operate='N';
	base[0].extend='Y';
	base[0].father=-1;
	for(i=0;n<4000;i++)
	{
		if(base[i].extend=='Y')
		{
			if(base[i].operate=='L')
			{
				right(i);up(i);down(i);
			}
			if(base[i].operate=='R')
			{
				left(i);up(i);down(i);
			}
			if(base[i].operate=='U')
			{
				left(i);right(i);down(i);
			}
			if(base[i].operate=='D')
			{
				left(i);right(i);up(i);
			}
			if(base[i].operate=='N')
			{
				left(i);right(i);up(i);down(i);
			}
		}
	}
}