//Global constant define

#define MaxStep  500000


#include <math.h>
#include <iostream.h>

//Global varibal define

int iCurrentElement = 1, iStep = 0;
bool bSucceed = false;

struct bsm
{
  int s[3][3];
  int me ;
  int father;
  int level;
  int posX,posY;
}  src[MaxStep],destnation;

void print(bsm dest)
{
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
			cout << dest.s[i][j] << "  ";
		cout << '\n';
	}
}

int compare(bsm src,bsm dest)
{
	for(int i=0;i<3 ; i++)
		for(int j=0; j <3 ; j++)
			if (src.s[i][j] != dest.s[i][j])
				return 0;

	return 1;
}


void copy (bsm &src,bsm &dest)
{
	dest.father = src.father;
	dest.level  = src.level;
	dest.posX   = src.posX;
	dest.posY   = src.posY;
	dest.me     = src.me;
	for(int i = 0 ; i < 3 ; i++)
		for(int j = 0 ; j < 3 ; j++)
			dest.s[i][j] = src.s[i][j];
}


int step(bsm temp)
{
	bool exist ;
	for(int i=0;i < 4 ; i++)
	{
		bsm dest;
		copy(temp ,dest);
		int j = ((((i+1) % 2) ? dest.posX :dest.posY) + ((i < 2 ) ? 1 : -1));
		if (j < 0 || j > 2)
		{
			continue;
		}
		else
		{
			exist = false;
			if ((i+1) % 2) 
			{
				dest.s[dest.posX][dest.posY] = dest.s[j][dest.posY];
				dest.s[j][dest.posY] = 0;
				dest.posX = j;
			}
			else
			{
				dest.s[dest.posX][dest.posY] = dest.s[dest.posX][j];
				dest.s[dest.posX][j] = 0;
				dest.posY = j;
			}

			dest.father = dest.me;
			dest.level += 1;
			dest.me     = iCurrentElement;

			for (int i = iCurrentElement ; i >= 0; i--)
			{
				if(compare(dest ,src[i]))
				{
					exist = true;
					break;
				}
			}
			if(exist)
				continue;

			if(iCurrentElement >= MaxStep)
				return 1;

			copy ( dest , src[iCurrentElement] );

			++iCurrentElement;

			if (compare(dest,destnation))
			{
				bSucceed = true;
				break;
			}

		}
	}
}


int Init()
{

	for(int i=0;i<3 ; i++)
	{
		for(int j=0; j <3 ; j++)
		{
			destnation.s[i][j] =  ((( ( i * 3) )  + (j+1) ) % 9 );
			cin >> src[0].s[i][j];
			if (src[0].s[i][j] < 0 || src[0].s[i][j] >8)
			{
				cout <<"Are you kidding? I can only recive the number between(include) 0 and 8! " 
					 << endl;
				return 0;
			}
			if (src[0].s[i][j] == 0)
			{
				src[0].posX = i ;
				src[0].posY = j ;
			}
		}
	}

	destnation.posX   = 2 ;
	destnation.posY   = 2 ;
	destnation.level  = 0 ;
	destnation.father = -1 ;

	src[0].level  = 0 ;
	src[0].father = -1 ;
	src[0].me     = 0  ;

	for(int k = 1 ; k < MaxStep ; k++)
		src[k].father = -2 ;

    iCurrentElement = 1;
	iStep = 0;
    bSucceed = false;


	return 1;
		
}

void layout(int myself)
{


	if(src[myself].father != -1) 
		layout(src[myself].father);
	cout << "Step " << ++iStep << ':' << endl;
	print(src[myself]);
/*
	for(int i = 0 ; src[i].father != -2 ; i ++)
	{
		cout << "Step " << i+1 << " :" <<endl;
		print(src[i]);
	}

*/

}


void example()
{

	src[0].s[0][0] = 1;
	src[0].s[0][1] = 2;
	src[0].s[0][2] = 3;
	src[0].s[1][0] = 7;
	src[0].s[1][1] = 4;
	src[0].s[1][2] = 5;
	src[0].s[2][0] = 8;
	src[0].s[2][1] = 0;
	src[0].s[2][2] = 6;
	src[0].level   = 0;
	src[0].father  = -1;
	src[0].me      = 0;
	src[0].posX    = 2;
	src[0].posY    = 1;

	for(int i=0;i<3 ; i++)
		for(int j=0; j <3 ; j++)
			destnation.s[i][j] =  ((( ( i * 3) )  + (j+1) ) % 9 );

	destnation.posX   = 2 ;
	destnation.posY   = 2 ;
	destnation.level  = 0 ;
	destnation.father = -1 ;

	for(int j = 0 ; !bSucceed  && iCurrentElement < MaxStep ; j++)
	{
		step(src[j]);
	}

	if(iCurrentElement == MaxStep)
	{
		cout << "Sorry the stupid programer who designed me didn't give enough space . so , i can't give you the answer!" << endl;
	}
	else
		layout(src[iCurrentElement-1].me);


}

void main()
{

	cout << "     八數碼問題 \n"  << endl << endl << "問題描述：\n";
	cout << "有一個3*3的棋盤，其中有0-8 9個數字，0表示空格，其他的數字可以和0交換位置。" << endl ;
	cout << "求由初始狀態 : \n" << "1  2  3 \n4  5  6\n7  8  0 \n" << "到達目標狀態步數最少的解。\n";
	cout << "輸入方法舉例：\n" << "從鍵盤輸入：\n" << "1 2 3 7 4 5 8 0 6\n" ;
	cout << "則向屏幕輸出:\n";

	example();

	cout << "現在請輸入你的數據：\n";

	if(!Init())
	{
		cout << "I can't initial !";
		return;
	}

	if(compare(src[0],destnation))
	{
		cout << "哥們兒，開玩笑呢，干嘛直接輸入目標狀態!" <<endl;
		return;
	}


	for(int j = 0 ; !bSucceed  && iCurrentElement < MaxStep ; j++)
	{
		step(src[j]);
	}

	if(iCurrentElement == MaxStep)
	{
		cout << "Sorry the stupid programer who designed me didn't give me enough space . so , i can't give you the answer!";
		cout << "even I have compute " << src[iCurrentElement-1].level << "steps!";

	}

	else
		layout(src[iCurrentElement-1].me);

	cout << endl <<"Used " << iCurrentElement - 1 << " array element," << " in " << src[iCurrentElement - 1].level << " steps" <<endl;


}