#include<iostream.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define size 3

long total;
typedef char board[size][size];
board target = {1,2,3,8,0,4,7,6,5};		// 目標狀態
class Node{
public:
	board data;		//存放狀態
	Node *parent;	//存放父節點地址
	Node *child[4];	//存放子節點地址,最多4個
	Node *next;
	int f,h,g,how;	//how中記錄了其父節點如何移動生成該節點

	Node();
	int geth();
};
Node::Node()//構造函數
{
	parent=NULL;
	next=NULL;
	for(int i=0;i<4;i++){
		child[i]=NULL;
	}
	h=0;g=0;how=0;f=0;
}
int Node::geth()//計算h值(h值為每個將牌與其目標位的總和)
{
	int h=0;
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
			for(int x=0;x<size;x++)
				for(int y=0;y<size;y++)
					if(target[x][y]==this->data[i][j]&&target[x][y]!=0)
							h+=abs(x-i)+abs(y-j);
					return h;
}

/***************************************************************/
bool can_solve(Node *start) {					// 搜索前判斷是否可解
	long i,j,k1,k2;
	for (i=0; i<size; i++) for (j=0; j<size; j++) {
		if (start->data[i][j]==0) {
			start->data[i][j] = size*size;
			k1 = (size-1-i) + (size-1-j);
		}
		if(target[i][j]==0){
			target[i][j] = size*size;
			k2 = (size-1-i) + (size-1-j);
		}
	}
	for (i=0; i<size*size; i++) for (j=i+1; j<size*size; j++) {
		if (start->data[i/size][i%size] > start->data[j/size][j%size]) k1++;		
		if (target[i/size][i%size] > target[j/size][j%size]) k2++;		
	}
	for (i=0; i<size; i++) for (j=0; j<size; j++) {
		if (start->data[i][j]==size*size) start->data[i][j]=0;		
		if (target[i][j]==size*size) target[i][j]=0;		
	}
	return (k1%2)==(k2%2);
}
Node *head;
//判斷temp狀態是否是目標狀態
bool goal(board temp)
{
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
			if(temp[i][j]!=target[i][j])
				return false;
			return true;
}
//返回0所在的坐標
void getxy(Node *temp,int &x,int &y){
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
			if(temp->data[i][j]==0){
				x=i;
				y=j;
			}
}
//擴展p所指向的節點
void Expand(Node *p){
	int x,y;
	getxy(p,x,y);
	int i=0;
	//y!=0(左邊有節點)并且how!=4(不是父節點右移得到的),進行左移
	if(y!=0&&p->how!=4){
		p->child[i]=new Node;
		for(int k=0;k<size;k++)
			for(int j=0;j<size;j++)
				p->child[i]->data[k][j]=p->data[k][j];
		p->child[i]->data[x][y]=p->data[x][y-1];
		p->child[i]->data[x][y-1]=0;
		p->child[i]->parent=p;
		p->child[i]->h=p->child[i]->geth();
		p->child[i]->g=p->g+1;
		p->child[i]->how=1;
		p->child[i]->f=p->child[i]->h+p->child[i]->g;
		i++;
		total++;
	}
	if(y!=2&&p->how!=1){
		p->child[i]=new Node;
		
		for(int k=0;k<size;k++)
			for(int j=0;j<size;j++)
				p->child[i]->data[k][j]=p->data[k][j];

		p->child[i]->data[x][y]=p->data[x][y+1];
		p->child[i]->data[x][y+1]=0;

		p->child[i]->parent=p;
		p->child[i]->h=p->child[i]->geth();
		p->child[i]->g=p->g+1;
		p->child[i]->how=4;
		p->child[i]->f=p->child[i]->h+p->child[i]->g;
		i++;
		total++;
	}
	if(x!=0&&p->how!=3){
		p->child[i]=new Node;
		
		for(int k=0;k<size;k++)
			for(int j=0;j<size;j++)
				p->child[i]->data[k][j]=p->data[k][j];

		p->child[i]->data[x][y]=p->data[x-1][y];
		p->child[i]->data[x-1][y]=0;

		p->child[i]->parent=p;
		p->child[i]->h=p->child[i]->geth();
		p->child[i]->g=p->g+1;
		p->child[i]->how=2;
		p->child[i]->f=p->child[i]->h+p->child[i]->g;
		i++;
		total++;
	}
	if(x!=2&&p->how!=2){
		p->child[i]=new Node;
		
		for(int k=0;k<size;k++)
			for(int j=0;j<size;j++)
				p->child[i]->data[k][j]=p->data[k][j];

		p->child[i]->data[x][y]=p->data[x+1][y];
		p->child[i]->data[x+1][y]=0;

		p->child[i]->parent=p;
		p->child[i]->h=p->child[i]->geth();
		p->child[i]->g=p->g+1;
		p->child[i]->how=3;
		p->child[i]->f=p->child[i]->h+p->child[i]->g;
		i++;
		total++;
	}//插入open表
	for(int j=0;j<i;j++){
		if(head==NULL||head->f>=p->child[j]->f){
			Node *temp=head;
			head=p->child[j];
			p->child[j]->next=temp;
		}
		else{
			Node *temp=head;
			Node *oldtemp=temp;
			while(temp!=NULL&&temp->f<p->child[j]->f){
				oldtemp=temp;
				temp=temp->next;
			}
			if(temp==NULL||oldtemp->next==NULL){
				oldtemp->next=p->child[j];
				p->child[j]->next=NULL;
			}
			else{
				oldtemp->next=p->child[j];
				p->child[j]->next=temp;
			}
		}
	}
	p->next=head;
}

void main(){
	int i,j,k;
	double totaltime;
	double fenzhi=0;
	double fenmu=0;
	int cs;
	char ch;
	//scanf("%ld", &cs);
	cs = 1;
	while (true)
	{
		total=1;
		//輸入原始狀態
		Node begin;
		Node *start=&begin;
		printf("\n請選擇:\na.手動輸入\nb.隨機生成\n");
			scanf(" %c",&ch);
		if(ch=='a'){
			printf("\n請輸入初始狀態:\n");
			for (i=0;i<size;i++)for(j=0;j<size;j++){
				scanf("%ld",&k);
				start->data[i][j] = k;
			}
		}
		else{
			srand((unsigned)time(NULL));     //隨機時間種子
			int a[9];
			for(i=0;i<size;i++)
				for(j=0;j<size;j++){
				   k=int(rand())%9;
				   start->data[i][j]=k;
				   a[i*size+j]=k;
					  for(k=0;k<i*size+j&&(i+j)!=0;k++)
						  if(start->data[i][j]==a[k]) {
							  j--; 
							  break;
						  }
				}
		}
		printf("\n初始狀態為:\n");
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++)
				printf("%d ",start->data[i][j]);
			printf("\n");
		}
		printf("是否要修改目標狀態?(y/n):\n");
		scanf(" %c",&ch);
		if(ch=='Y'||ch=='y')
		{
			printf("請輸入新的目標狀態:\n");
			for (i=0;i<size;i++)
				for(j=0;j<size;j++) {
					scanf("%ld",&k);
					target[i][j] = k;
			}
		}
		    //判斷是否能到目標狀態
			if (!can_solve(start)) { 
				printf("This puzzle is not solvable.\n"); 
				continue; 
			}//對原始狀態節點進行初始化
			fenzhi=0;
			fenmu=0;
			totaltime=double(clock());
			start->g=0;
			start->h=start->geth();
			start->how=0;
			start->f=start->h+start->g;
			head=start;
			//加入open表,head為頭指針

			while(true){
				if(goal(head->data))
					break;
				//將tempn(原來的head)從open表中刪除
				Node *tempn=head;
				head=head->next;
				//擴展tempn
				Expand(tempn);
				fenmu=fenmu+1;
				//對open表進行排序
				i=0;
				fenzhi=fenzhi+1;
				while(tempn->child[i]!=NULL&&i<4){
						i++;
						fenzhi=fenzhi+1;				
				}
			}
			printf("\n%2.10f ",totaltime);
			totaltime=(double(clock())-totaltime)/CLOCKS_PER_SEC;
			printf("\n%2.10f \n",double(clock()));
			fenzhi=fenzhi/fenmu;
			j=-1;
			//輸出結果
			while(head!=NULL){
				for(int i=0;i<size;i++){
					for(int j=0;j<size;j++)
						printf("%d ",head->data[i][j]);
					printf("\n");
				}
					head=head->parent;
					printf("  ^ \n");
					j++;
			}
			printf("總共%d步！\n",j);
			printf( "運行時間: %2.8f seconds\n", totaltime);
			printf("生成節點數:%8ld\n",total);
			printf("平均分枝因子:%f\n",fenzhi);
			start=start->next;
			while(start!=NULL){
				Node *temp=start;
				start=start->next;
				delete temp;
			}
			printf("\n繼續?(y/n):");
			scanf(" %c",&ch);
			if(ch=='n'||ch=='N'){
				break;
			}
		}
}