#include <iostream>
using namespace std;
static int target[9]={1,2,3,4,5,6,7,8,0};
class eight{
public:
	eight* parent;
	eight* next;
	eight* pre;
    eight(int init_num[9]);
	eight(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9){
        num[0]=num1;
		num[1]=num2;
		num[2]=num3;
		num[3]=num4;
		num[4]=num5;
		num[5]=num6;
		num[6]=num7;
		num[7]=num8;
		num[8]=num9;
	}
	eight(void){
		for(int i=0;i<9;i++)
			num[i]=i;
	}
	void cul_para(void);
	void get_numbers_to(int other_num[9]);
	int get_nipn(void){
		return not_in_position_num;
	}
	int get_deapth(void){
		return deapth;
	}
	int get_evafun(void){
		return eva_function;
	}
	void set_num(int other_num[9]);
	void show(void);
	eight& operator=(eight&);
	eight& operator=(int other_num[9]);
	int operator==(eight&);
	int operator==(int other_num[9]);
private:
	int num[9];
	int not_in_position_num;
	int deapth;
	int eva_function;
};
void eight::cul_para(void){
	int i;
	int temp_nipn=0;
	for (i=0;i<9;i++)
		if (num[i]!=target[i])
			temp_nipn++;
		not_in_position_num=temp_nipn;
		if (this->parent==NULL)
			deapth=0;
		else
			deapth=this->parent->deapth+1;
		eva_function=not_in_position_num+deapth;
}
eight::eight(int init_num[9]){
	for (int i=0;i<9;i++)
		num[i]=init_num[i];
}
void eight::show(){
	for(int i=0;i<9;i++){
		cout<<num[i];
		cout<<" ";
		if(i==2||i==5||i==8)cout<<"\n";
	}
}
void eight::get_numbers_to(int other_num[9]){
	for (int i=0;i<9;i++)
		other_num[i]=num[i];
}
void eight::set_num(int other_num[9]){
	for(int i=0;i<9;i++)
		num[i]=other_num[i];
}
eight& eight::operator=(eight& another_8num){
	for(int i=0;i<9;i++)
		num[i]=another_8num.num[i];
	not_in_position_num=another_8num.not_in_position_num;
	deapth=another_8num.deapth+1;
	eva_function=not_in_position_num+deapth;
	return *this;
}
eight& eight::operator=(int other_num[9]){
	for(int i=0;i<9;i++)
		num[i]=other_num[i];
	return *this;
}
int eight::operator==(eight& another_8num){
	int match=1;
	for(int i=0;i<9;i++)
		if(num[i]!=another_8num.num[i]){
			match=0;
			break;
		}
		if(match==0)
			return 0;
		else return 1;
}
int eight::operator==(int other_num[9]){
	int match=1;
	for(int i=0;i<9;i++)
		if(num[i]!=other_num[i]){
			match=0;
			break;
		}
		if(match==0)
			return 0;
		else return 1;
}
//空格向上移
int move_up(int num[9]){
	for(int i=0;i<9;i++)
		if(num[i]==0) break;
		if(i<3) return 0;
		else{
		num[i]=num[i-3];
		num[i-3]=0;
		return 1;
		}
}
//空格向下移
int move_down(int num[9]){
	for(int i=0;i<9;i++)
		if(num[i]==0)
			break;
		if(i>5)return 0;
		else{
		num[i]=num[i+3];
		num[i+3]=0;
		return 1;
		}
}
//空格向左移
int move_left(int num[9]){
	for(int i=0;i<9;i++)
		if(num[i]==0)
			break;
		if(i==0||i==3||i==6)
			return 0;
		else{
			num[i]=num[i-1];
			num[i-1]=0;
			return 1;
		}
}
//空格向右移
int move_right(int num[9]){
	for(int i=0;i<9;i++)
		if(num[i]==0)
			break;
		if(i==2||i==5||i==8)
			return 0;
		else{
			num[i]=num[i+1];
		    num[i+1]=0;
		    return 1;
		}
}
//判斷可否解出
int icansolve(int num[9],int target[9]){
	int i,j;
	int count_num,count_target;
	for(i=0;i<9;i++)
		for (j=0;j<i;j++){
			if(num[j]<num[i]&&num[j]!=0)
				count_num++;
			if(target[j]<target[i]&&target[j]!=0)
				count_target++;
		}
		count_num=count_num-2*(count_num/2);
	    count_target=count_target-2*(count_target/2);
		if((count_num==1&&count_target==1)||(count_num==0&&count_target==0))
			return 1;
		else
			return 0;
}
//判斷有無重復(fù)
int existed(int num[9],eight *where){
	eight *p;
	for(p=where;p!=NULL;p=p->parent)
		if(*p==num)
			return 1;
		return 0;
}
//尋找估價(jià)函數(shù)最小的葉子節(jié)點(diǎn)
eight* find_OK_leaf(eight* start){
	eight *p,*OK;
	p=OK=start;
	int min=start->get_evafun();
	for(p=start;p!=NULL;p=p->next)
		if(min>p->get_evafun()){
			OK=p;
			min=p->get_evafun();
		}
		return OK;
}
//主函數(shù)開始
int main(void){
	int num[9];
	int flag=0;//是否輸入錯(cuò)誤標(biāo)志，1表示輸入錯(cuò)誤
	int bingo=0;//是否查找成功標(biāo)志，1表示成功
	int i,j;
	cout<<"Please input the number(0 for the blank):\n";
	for(i=0;i<9;i++){
		flag=0;
		cin>>num[i];
		for(j=0;j<i;j++)
			if(num[i]==num[j])
				flag=1;
			if(num[i]<0||num[i]>8||flag==1){
				i--;
				cout<<"input error,please input again!"<<endl;
			}
	}
	eight S(num),Target(target);
	S.parent=S.next=S.pre=NULL;
	S.cul_para();
	cout<<"Now the initial numbers are:"<<endl;;
	S.show();
	cout<<"And the Target is:"<<endl;
	Target.show();
	eight *OK_leaf=&S,*leaf_start=&S,*new_8num,*p;
	while(OK_leaf!=NULL&&bingo!=1){
		OK_leaf=find_OK_leaf(leaf_start);
		if(*OK_leaf==Target){
			bingo=1;
			break;
		}
		p=OK_leaf->pre;
		OK_leaf->get_numbers_to(num);
		if(move_up(num)&&!existed(num,OK_leaf)){
			new_8num=new eight;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->pre=p;
			if(p==NULL) leaf_start=new_8num;
			else
				p->next=new_8num;
			p=new_8num;
		}
		OK_leaf->get_numbers_to(num);
		if(move_down(num)&&!existed(num,OK_leaf)){
			new_8num=new eight;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->next=new_8num;
			    p=new_8num;
		}
		OK_leaf->get_numbers_to(num);
		if(move_left(num)&&!existed(num,OK_leaf)){
			new_8num=new eight;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->next=new_8num;
			    p=new_8num;
		}
		OK_leaf->get_numbers_to(num);
		if(move_right(num)&&!existed(num,OK_leaf)){
			new_8num=new eight;			
			new_8num->set_num(num);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->next=new_8num;
			    p=new_8num;
		}
		p->next=OK_leaf->next;
		if(OK_leaf->next!=NULL)
			OK_leaf->next->pre=p;
		OK_leaf->next=OK_leaf->pre=NULL;
	}
	if(bingo==1){
		eight *p;
		for(p=OK_leaf->parent;p!=NULL;p=p->parent){
			cout<<endl;
			p->show();
		}
	}else cout<<"Fail to find!";
	return 0;
}