#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int factor[3][3]={1,2,6,40320,1,24,5040,720,120};    //計算狀態(tài)hash值時對每位賦予的權(quán)重（階乘形式）
static int pos[9][2]={{0,0},{0,0},{0,1},{0,2},{1,2},{2,2,},{2,1},{2,0},{1,0}};//計算曼哈頓距離時用來表示數(shù)碼的相應(yīng)目標(biāo)位置
static int f_state[3][3]={1,2,3,8,0,4,7,6,5};//終止?fàn)顟B(tài)
int state[362880]={0};//hash判重

struct Node{                           //定義節(jié)點(diǎn)結(jié)構(gòu)體
	int NO[3][3];              //八數(shù)碼位置
	int depth;                 //節(jié)點(diǎn)所處搜索深度
	int cost;                  //估價結(jié)果
	struct Node * parent;     //指向父節(jié)點(diǎn)的指針
};
typedef struct Node node;

struct queue{                            //存放open表的隊(duì)列
	node * h;
	struct queue * next;
};
typedef struct queue Queue;

int h(node n){      //啟發(fā)函數(shù)f*(n)的計算
	int sum=0;
	int i,j;
	int t;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(t=n.NO[i][j]){
				sum+=(i>pos[t][0])?(i-pos[t][0]):(pos[t][0]-i);
				sum+=(j>pos[t][1])?(j-pos[t][1]):(pos[t][1]-j);                 //曼哈頓距離
			}
	return sum;
}

int solved(node n){                     //判斷是否完成搜索
	int i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(n.NO[i][j]!=f_state[i][j])
				return 0;
	return 1;
}
	
int hash(node n){      //hash值的計算
	int i,j;
	int hashnum=0;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			hashnum+=(n.NO[i][j]*factor[i][j]);    //對應(yīng)位與相應(yīng)權(quán)重相乘
	return hashnum;
}

void findspace(node n,int a[2]){   //找到空格的位置
	int i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			if(!n.NO[i][j]){
				a[0]=i;
				a[1]=j;
				return ;
			}
}

void exchange(node * &n,int a[2],int i,int j){    //空格移動，移動的方向由i,j控制
	int m,l;
	m=a[0];
	l=a[1];
	n->NO[m][l]=n->NO[m+i][l+j];
	n->NO[m+i][l+j]=0;
	m=hash(*n);                      
	if(state[m])                    //hash判重
		n=NULL;
	else
		state[m]=1;
}

void EnQueue(Queue * &head,Queue * &tmp){   //采用插入排序向open表隊(duì)列中加入子節(jié)點(diǎn)
	Queue *p,*q;
	int t;
	t=tmp->h->cost;
	p=head->next;
	q=head;
	while(p&&p->h->cost<t){    //使得代價最小的節(jié)點(diǎn)排在隊(duì)列首部
		p=p->next;
		q=q->next;
	}
	if(p){
		tmp->next=p;
		q->next=tmp;
	}
	else{
		tmp->next=NULL;
		q->next=tmp;
	}
}

void nodeprint(node n){                                                       //打印節(jié)點(diǎn)信息
	int i,j;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++)
			if(n.NO[i][j])
				printf("%d",n.NO[i][j]);
			else
				putchar(' ');
		printf("\n");
	}
	printf("*******\n");
}
void print(node n,node s0){    //遞歸打印搜索過程
	if(memcmp((const void *)(n.NO),(const void *)(s0.NO),36)){
		print(*(n.parent),s0);
		nodeprint(n);	
	}
	else
		nodeprint(n);
}

void addopen(node * current,Queue * &head,int position[],int i,int j){      //生成子節(jié)點(diǎn)，并加入到open表中
	node * temp;
	Queue * tmp;
	temp=(node *)malloc(sizeof(node));
	*temp=*current;
	temp->parent=current;
	temp->depth=current->depth+1;
	exchange(temp,position,i,j);
	if(temp){
		temp->cost=temp->depth+h(*temp);
		tmp=(Queue *)malloc(sizeof(Queue));
		tmp->h=temp;
		tmp->next=NULL;
		EnQueue(head,tmp);
	}
}

int main(void){
	node *s0,*current;
	int i,j;
	int flag=0;
	Queue * head;
	printf("請從上至下，從左至右輸入八數(shù)碼圖中各位置的數(shù)值，空格用0表示：\n");
	s0=(node *)malloc(sizeof(node));                                //初始狀態(tài)節(jié)點(diǎn)
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			scanf("%d",&(s0->NO[i][j]));
	s0->depth=0;    
	s0->cost=s0->depth+h(*s0);
	s0->parent=NULL;
	state[hash(*s0)]=1;
	head=(Queue *)malloc(sizeof(Queue));                  //初始化open表隊(duì)列
	head->next=NULL;
	current=s0;
	while(!solved(*current)){
		int position[2];
		findspace(*current,position);                            //找到空格位置
		if(position[0]>=1)                                       //空格向四個方向移動生成子節(jié)點(diǎn)，向上
			addopen(current,head,position,-1,0);
		if(position[0]<=1)                                       //向下
			addopen(current,head,position,1,0);
		if(position[1]<=1)                                       //向右
			addopen(current,head,position,0,1);
		if(position[1]>=1)                                       //向左
			addopen(current,head,position,0,-1);
		if(head->next!=NULL){
			current=head->next->h;                            //取出隊(duì)列首部節(jié)點(diǎn)，繼續(xù)下一次循環(huán)
			head->next=head->next->next;
		}
		else{
			flag=1;                                    //若隊(duì)列空，則無解
			break;
		}
	}
	if(flag)
		printf("無解！！！\n");
	else
		print(*current,*s0);
	return 0;
}