// JiuG.cpp: implementation of the CJiuG class.

#include "stdafx.h"
#include "Jiugong.h"
#include "JiuG.h"
#include "math.h"//計(jì)算估價(jià)函數(shù)是會(huì)用到abs()，如果用錯(cuò)位數(shù)，則不用包含
#include "stdlib.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CJiuG::CJiuG()
{
	m_ndepth=100;//設(shè)置默認(rèn)的深度為100，可以在程序中改動(dòng)
}

CJiuG::~CJiuG()
{

}

/////////////////////////////////////////////////////////////////////
//左移
bool CJiuG::MoveLeft(JGState *src,JGState *result)
{
	int x,y,tempx,tempy;
	for(x=0;x<3;x++){
		for(y=0;y<3;y++){
			if(src->state[x][y]==0){
				tempx=x;
				tempy=y;
			}
		}
	}

	if(tempy==0)
		return false;

	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			result->state[i][j]=src->state[i][j];
		}
	}
	
	result->state[tempx][tempy] = src->state[tempx][tempy-1];
	result->state[tempx][tempy-1] = 0;
	result->curdistance=src->curdistance+1;
	result->prestate=src;
	result->nextstate=NULL;

	return true;
}

////////////////////////////////////////////////////////////////////
//右移
bool CJiuG::MoveRight(JGState *src,JGState *result)
{
	int x,y,tempx,tempy;
	for(x=0;x<3;x++){
		for(y=0;y<3;y++){
			if(src->state[x][y]==0){
				tempx=x;
				tempy=y;
			}
		}
	}

	if(tempy==2)
		return false;

	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			result->state[i][j]=src->state[i][j];
		}
	}

	result->state[tempx][tempy]=src->state[tempx][tempy+1];
	result->state[tempx][tempy+1]=0;
	result->curdistance=src->curdistance+1;
	result->prestate=src;
	result->nextstate=NULL;

	return true;
}

///////////////////////////////////////////////////////////////////
//上移，上面的左移，右移，下面的下移，結(jié)構(gòu)一樣
bool CJiuG::MoveUp(JGState *src,JGState *result)
{
	int x,y,tempx,tempy;
	//尋找空格位置
	for(x=0;x<3;x++){
		for(y=0;y<3;y++){
			if(src->state[x][y]==0){
				tempx=x;
				tempy=y;
			}
		}
	}

	//判斷是否可移
	if(tempx==0)
		return false;

	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			result->state[i][j]=src->state[i][j];
		}
	}

	result->state[tempx][tempy]=src->state[tempx-1][tempy];
	result->state[tempx-1][tempy]=0;
	result->curdistance=src->curdistance+1;//深度加一
	result->prestate=src;//設(shè)置前趨節(jié)點(diǎn)
	result->nextstate=NULL;

	return true;
}

////////////////////////////////////////////////////////////////////
//下移
bool CJiuG::MoveDown(JGState *src,JGState *result)
{
	int x,y,tempx,tempy;
	for(x=0;x<3;x++){
		for(y=0;y<3;y++){
			if(src->state[x][y]==0){
				tempx=x;
				tempy=y;
			}
		}
	}

	if(tempx==2)
		return false;

	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			result->state[i][j]=src->state[i][j];
		}
	}

	result->state[tempx][tempy]=result->state[tempx+1][tempy];
	result->state[tempx+1][tempy]=0;
	result->curdistance=src->curdistance+1;
	result->prestate=src;
	result->nextstate=NULL;

	return true;
}

///////////////////////////////////////////////////////////////////
//比較兩個(gè)狀態(tài)是否相等
bool CJiuG::Compare(JGState *src1,JGState *src2)
{
	for(int i=0;i<=2;i++){
		for(int j=0;j<=2;j++){
			if(src1->state[i][j]!=src2->state[i][j])
				return false;
		}
	}

	return true;
}

///////////////////////////////////////////////////////////////////
//計(jì)算估價(jià)函數(shù)，采用了每一步移到正確的位置需要的步數(shù)
int CJiuG::ComputeFn(JGState *cur,JGState *dest)
{
	int xcur[9],ycur[9],xdest[9],ydest[9];//保存9個(gè)坐標(biāo)
	int i,j;
	int result=0;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			xcur[cur->state[i][j]]=i;
			ycur[cur->state[i][j]]=j;
			xdest[dest->state[i][j]]=i;
			ydest[dest->state[i][j]]=j;
		}
	}

	for(i=1;i<9;i++){
		result=result+abs(xcur[i]-xdest[i])+abs(ycur[i]-ydest[i]);
	}

	return result;
	/*int result=0;//注釋掉的部分是采用了錯(cuò)位數(shù)來計(jì)算
	int i,j;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			if(cur->state[i][j]!=dest->state[i][j])
				result++;
		}
	}

	return result;*/
}


///////////////////////////////////////////////////////////////////
//搜索最優(yōu)解，這是程序的核心部分
bool CJiuG::Search()
{
	int MAXDEPTH=m_ndepth;
	FreeList(&OpenList);
	FreeList(&CloseList);
	FreeList(&ResultList);
	JGState *newstate,*pstart;
	int i,k;
	newstate=(JGState *)malloc(sizeof(JGState));
	CopyJG(&StateInit,newstate);
	newstate->curdistance=0;
	newstate->nextstate=NULL;
	newstate->prestate=NULL;
	pstart=newstate;
	curstep=pstart;
	//如果初始狀態(tài)和末態(tài)相同，搜索成功退出
	if(Compare(&StateInit,&StateObj)==true){
		ResultList.AddTail((void *)newstate);
		return true;
	}
	
	//將起始結(jié)點(diǎn)加入Open表中
	OpenList.AddHead((void *)newstate);
	
	//搜索
	while(true){
		JGState *pmin;
		int nmin;
		int nindex=0;
		//Open表為空，失敗退出
		if(OpenList.IsEmpty())
			return false;
		i=OpenList.GetCount();
		nmin=100000000;
		//搜索Open表中估計(jì)值最小的節(jié)點(diǎn)
		for(k=0;k<i;k++){
			JGState *ptemp;
			ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
			int ntemp=ptemp->curdistance+ComputeFn(ptemp,&StateObj);
			if(ntemp<nmin){
				nmin=ntemp;
				pmin=ptemp;
				nindex=k;
			}
		}
	
		//將估價(jià)函數(shù)最小的節(jié)點(diǎn)從Open表刪除，加入到Close表中
		OpenList.RemoveAt(OpenList.FindIndex(nindex));
		CloseList.AddTail((void *)pmin);

		newstate=(JGState *)malloc(sizeof(JGState));

		//move to left，用了搜索深度控制。下面的右移，上移，下移程序結(jié)構(gòu)相同
		//可以將相同的部分寫成函數(shù)，我沒有這樣做
		if((MoveLeft(pmin,newstate)==true)&&(newstate->curdistance<=MAXDEPTH)){
			if((Compare(newstate,&StateObj)==false)){
				//不是目標(biāo)節(jié)點(diǎn)，則看是否可以加入到Open表中
				bool inopen=false;
				bool inclose=false;
				JGState *ptemp;
				//檢查是否在Open表中
				i=OpenList.GetCount();
				if(i==0)
					inopen=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inopen=true;
							if(ptemp->curdistance>newstate->curdistance)
								CopyJG(newstate,ptemp);
							break;
						}
					}
				}
				//檢查是否在Close表中
				i=CloseList.GetCount();
				if(i==0)
					inclose=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inclose=true;
							break;
						}
					}
				}
				if((inopen==false)&&(inclose==false))
					OpenList.AddHead(newstate);
			}//end if
			else{
				//找到目標(biāo)結(jié)點(diǎn)
				JGState *newstate1;
				ResultList.AddHead((void *)newstate);
				newstate=newstate->prestate;
				//回溯，得到ResultList
				while(newstate!=pstart){
					newstate1=(JGState *)malloc(sizeof(JGState));
					CopyJG(newstate,newstate1);
					ResultList.AddHead(newstate1);
					newstate=newstate->prestate;
				}
				newstate1=(JGState *)malloc(sizeof(JGState));
				CopyJG(newstate,newstate1);
				ResultList.AddHead(newstate1);
				return true;
			}//end else
		}//end if 
		else{
			free(newstate);
		}//end move left

		newstate=(JGState *)malloc(sizeof(JGState));

		//move to right
		if(MoveRight(pmin,newstate)==true&&(newstate->curdistance<=MAXDEPTH)){
			if((Compare(newstate,&StateObj)==false)){
				//不是目標(biāo)節(jié)點(diǎn)，則看是否可以加入到Open表中
				bool inopen=false;
				bool inclose=false;
				JGState *ptemp;
				i=OpenList.GetCount();
				if(i==0)
					inopen=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inopen=true;
							if(ptemp->curdistance>newstate->curdistance)
								CopyJG(newstate,ptemp);
							break;
						}
					}
				}
				i=CloseList.GetCount();
				if(i==0)
					inclose=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inclose=true;
							break;
						}
					}
				}
				if((inopen==false)&&(inclose==false))
					OpenList.AddHead(newstate);
			}//end if
			else{
				//找到目標(biāo)結(jié)點(diǎn)
				JGState *newstate1;
				ResultList.AddHead((void *)newstate);
				newstate=newstate->prestate;
				while(newstate!=pstart){
					newstate1=(JGState *)malloc(sizeof(JGState));
					CopyJG(newstate,newstate1);
					ResultList.AddHead(newstate1);
					newstate=newstate->prestate;
				}
				newstate1=(JGState *)malloc(sizeof(JGState));
				CopyJG(newstate,newstate1);
				ResultList.AddHead(newstate1);
				return true;
			}//end else
		}//end if 
		else{
			free(newstate);
		}//end move right

		newstate=(JGState *)malloc(sizeof(JGState));

		//move to up
		if(MoveUp(pmin,newstate)==true&&(newstate->curdistance<=MAXDEPTH)){
			if((Compare(newstate,&StateObj)==false)){
				//不是目標(biāo)節(jié)點(diǎn)，則看是否可以加入到Open表中
				bool inopen=false;
				bool inclose=false;
				JGState *ptemp;
				i=OpenList.GetCount();
				if(i==0)
					inopen=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inopen=true;
							if(ptemp->curdistance>newstate->curdistance)
								CopyJG(newstate,ptemp);
							break;
						}
					}
				}
				i=CloseList.GetCount();
				if(i==0)
					inclose=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inclose=true;
							break;
						}
					}
				}
				if((inopen==false)&&(inclose==false))
					OpenList.AddHead(newstate);
			}//end if
			else{
				//找到目標(biāo)結(jié)點(diǎn)
				JGState *newstate1;
				ResultList.AddHead((void *)newstate);
				newstate=newstate->prestate;
				while(newstate!=pstart){
					newstate1=(JGState *)malloc(sizeof(JGState));
					CopyJG(newstate,newstate1);
					ResultList.AddHead(newstate1);
					newstate=newstate->prestate;
				}
				newstate1=(JGState *)malloc(sizeof(JGState));
				CopyJG(newstate,newstate1);
				ResultList.AddHead(newstate1);
				return true;
			}//end else
		}//end if 
		else{
			free(newstate);
		}//end move up

		newstate=(JGState *)malloc(sizeof(JGState));

		//move to down
		if(MoveDown(pmin,newstate)==true&&(newstate->curdistance<=MAXDEPTH)){
			if((Compare(newstate,&StateObj)==false)){
				//不是目標(biāo)節(jié)點(diǎn)，則看是否可以加入到Open表中
				bool inopen=false;
				bool inclose=false;
				JGState *ptemp;
				i=OpenList.GetCount();
				if(i==0)
					inopen=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)OpenList.GetAt(OpenList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inopen=true;
							if(ptemp->curdistance>newstate->curdistance)
								CopyJG(newstate,ptemp);
							break;
						}
					}
				}
				i=CloseList.GetCount();
				if(i==0)
					inclose=false;
				else{
					for(k=0;k<i;k++){
						ptemp=(JGState *)CloseList.GetAt(CloseList.FindIndex(k));
						if(Compare(newstate,ptemp)==true){
							inclose=true;
							break;
						}
					}
				}
				if((inopen==false)&&(inclose==false))
					OpenList.AddHead(newstate);
			}//end if
			else{
				//找到目標(biāo)結(jié)點(diǎn)
				JGState *newstate1;
				ResultList.AddHead((void *)newstate);
				newstate=newstate->prestate;
				while(newstate!=pstart){
					newstate1=(JGState *)malloc(sizeof(JGState));
					CopyJG(newstate,newstate1);
					ResultList.AddHead(newstate1);
					newstate=newstate->prestate;
				}
				newstate1=(JGState *)malloc(sizeof(JGState));
				CopyJG(newstate,newstate1);
				ResultList.AddHead(newstate1);
				return true;
			}//end else
		}//end if 
		else{
			free(newstate);
		}//end move down
	}
}

///////////////////////////////////////////////////////////////////
//釋放內(nèi)存
void CJiuG::FreeList(CPtrList *list)
{
	if(list->IsEmpty())
		return;
	int i=list->GetCount();
	JGState *p;
	for(int j=0;j<i;j++){
		p=(JGState *)list->GetHead();
		list->RemoveHead();
		free(p);
	}
}

void CJiuG::CopyJG(JGState *src,JGState *dest)
{
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			dest->state[i][j]=src->state[i][j];
		}
	}
	dest->curdistance=src->curdistance;
	dest->prestate=src->prestate;
	dest->nextstate=src->nextstate;
}

//////////////////////////////////////////////////////////////////
//計(jì)算逆序奇偶性，以判斷有無解，基于我對九宮問題解是否可達(dá)的證明
//返回0為偶，返回1為奇
int CJiuG::ComputeJO(JGState *jo)
{
	int result=0;
	int i,j;
	int k=0;
	int temp[8];
	//除去0，將其余8個(gè)數(shù)依次加入到數(shù)組中
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			if(jo->state[i][j]!=0){
				temp[k]=jo->state[i][j];
				k++;
			}
		}
	}
	//判斷奇偶性
	for(i=0;i<7;i++){
		for(j=i+1;j<8;j++){
			if(temp[i]>temp[j])
				result++;
		}
	}

	result=result%2;
	return result;
}