eightnums.cpp

利用VC开发的一个八数码程序

// EIGHTNUMS.cpp : implementation file
//

#include "stdafx.h"
#include "EightPuzzles.h"
#include "EIGHTNUMS.h"
#include "afxcoll.h"

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

/////////////////////////////////////////////////////////////////////////////
// CEIGHTNUMS dialog


CEIGHTNUMS::CEIGHTNUMS(CWnd* pParent /*=NULL*/)
	: CDialog(CEIGHTNUMS::IDD, pParent)
{
	//{{AFX_DATA_INIT(CEIGHTNUMS)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
}


void CEIGHTNUMS::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CEIGHTNUMS)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CEIGHTNUMS, CDialog)
	//{{AFX_MSG_MAP(CEIGHTNUMS)
	ON_BN_CLICKED(IDC_NEXTSTEP, OnNextstep)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CEIGHTNUMS message handlers

int CEIGHTNUMS::ComputeJiOu(NightProState *Jiou)
{
    int result =0;
	int i,j;
	int k=0;
	int temp[8];
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
		if(Jiou->state[i][j]!=0)
		{
			temp[k]=Jiou->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;

}

void CEIGHTNUMS::CopyNightNum(NightProState *cur, NightProState *dest)
{
   for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			dest->state[i][j]=cur->state[i][j];
		}
	}
	dest->curdistance=cur->curdistance;
	dest->laststate=cur->laststate;
	dest->nextstate=cur->nextstate; 

}

void CEIGHTNUMS::FreeList(CPtrList *list)
{
if(list->IsEmpty())
		return;
	int i=list->GetCount();
	NightProState *p;
	for(int j=0;j<i;j++)
	{
		p=(NightProState *)list->GetHead();
		list->RemoveHead();
		free(p);
	} 

}

bool CEIGHTNUMS::Search()
{
int MAXDEPTH=10000;
	FreeList(&Openlist);
	FreeList(&Closelist);
	FreeList(&ResultList);
	NightProState *newstate,*pstart;
	int i,k;
	newstate=(NightProState *)malloc(sizeof(NightProState));
	CopyNightNum(&IniState,newstate);
	newstate->curdistance=0;
	newstate->laststate=NULL;
	newstate->nextstate=NULL;
	pstart=newstate;
	currentstep=pstart;
	//如果始末状态相同，则成功退出
	if(Compare(&IniState,&ObjState)==true)
	{
		ResultList.AddTail((void *)newstate);
		return true;
	}
	//将初始节点加入Open表之中
	Openlist.AddHead((void *)newstate);
	//搜索
	while(true)
	{
		NightProState *pmin;
		int nmin;
		int nindex=0;
		//如果Open表为空，失败
		if(Openlist.IsEmpty())
			return false;
		i=Openlist.GetCount();
		nmin=100000000;
		//搜索Open表中估计值最小点
		for(k=0;k<i;k++)
		{
			NightProState *ptemp;
			ptemp=(NightProState *)Openlist.GetAt(Openlist.FindIndex(k));
			int ntemp=ptemp->curdistance+CompareFunction(ptemp,&ObjState);
			if(ntemp<nmin)
			{
				nmin= ntemp;
				pmin=ptemp;
				nindex=k;
			}
		}
		//将估价函数最小节点从Open表中删除，加入Result表中
		Openlist.RemoveAt(Openlist.FindIndex(nindex));
		ResultList.AddTail((void *)pmin);
		newstate=(NightProState *)malloc(sizeof(NightProState));

		//左移
		if((MoveLeft(pmin,newstate)==true) && (newstate->curdistance<=MAXDEPTH))
		{
			if((Compare(newstate,&ObjState)==false))
			{
				//如果不是目标节点，看是否可以加入到Open表中
				bool inopen=false;
				bool inclose =false;
				NightProState *ptemp;
				//检查是否在Open表之中
				i=Openlist.GetCount();
				if(i==0)
					inopen=false;
				else
				{
					for(k=0;k<i;k++)
					{
						ptemp=(NightProState *)Openlist.GetAt(Openlist.FindIndex(k));
						if(Compare(newstate,ptemp)==true)
						{
							inopen=true;
							if(ptemp->curdistance>newstate->curdistance)
								CopyNightNum(newstate,ptemp);
							break;
						}
					}
				}
				//检查是否在Result表之中
				i=ResultList.GetCount();
				if(i==0)
					inclose=false;
				else
				{
					for(k=0;k<i;k++)
					{
						ptemp=(NightProState *)ResultList.GetAt(ResultList.FindIndex(k));
						if(Compare(newstate,ptemp)==true)
						{
							inclose=true;
							break;
						}
					}
				}
				if((inopen==false)&&(inclose==false))
					Openlist.AddHead(newstate);
				
				else
				{
					//找到目标节点
					NightProState *newstate0;
					ResultList.AddHead((void *)newstate);
					newstate=newstate->laststate;
					while(newstate!=pstart)
					{
						newstate0=(NightProState *)malloc(sizeof(NightProState));
						CopyNightNum(newstate,newstate0);
						ResultList.AddHead(newstate0);
						newstate=newstate->laststate;
					}
					newstate0=(NightProState *)malloc(sizeof(NightProState));
					CopyNightNum(newstate,newstate0);
					ResultList.AddHead(newstate0);
					return true;
				}
			}
			else
			
				free(newstate);
			}
			newstate=(NightProState *)malloc(sizeof(NightProState));
		
			//右移
			if((MoveRight(pmin,newstate)==true) && (newstate->curdistance<=MAXDEPTH))
			{
				if((Compare(newstate,&ObjState)==false))
				{
					//如果不是目标节点，看是否可以加入到Open表中
					bool inopen=false;
					bool inclose =false;
					NightProState *ptemp;
					//检查是否在Open表之中
					i=Openlist.GetCount();
					if(i==0)
						inopen=false;
					else
					{
						for(k=0;k<i;k++)
						{
							ptemp=(NightProState *)Openlist.GetAt(Openlist.FindIndex(k));
							if(Compare(newstate,ptemp)==true)
							{
								inopen=true;
								if(ptemp->curdistance>newstate->curdistance)
									CopyNightNum(newstate,ptemp);
								break;
							}
						}
					}
					//检查是否在Result表之中
					i=ResultList.GetCount();
					if(i==0)
						inclose=false;
					else
					{
						for(k=0;k<i;k++)
						{
							ptemp=(NightProState *)ResultList.GetAt(ResultList.FindIndex(k));
							if(Compare(newstate,ptemp)==true)
							{
								inclose=true;
								break;
							}
						}
					}
					if((inopen==false)&&(inclose==false))
						Openlist.AddHead(newstate);
					
					else
					{
						//找到目标节点
						NightProState *newstate0;
						ResultList.AddHead((void *)newstate);
						newstate=newstate->laststate;
						while(newstate!=pstart)
						{
							newstate0=(NightProState *)malloc(sizeof(NightProState));
							CopyNightNum(newstate,newstate0);
							ResultList.AddHead(newstate0);
							newstate=newstate->laststate;
						}
						newstate0=(NightProState *)malloc(sizeof(NightProState));
						CopyNightNum(newstate,newstate0);
						ResultList.AddHead(newstate0);
						return true;
					}
				}
				else
				{
					free(newstate);
				}
				newstate=(NightProState *)malloc(sizeof(NightProState));
			}
				//上移
				if((MoveUp(pmin,newstate)==true)&& (newstate->curdistance<=MAXDEPTH))
				{
					if((Compare(newstate,&ObjState)==false))
					{
						//如果不是目标节点，看是否可以加入到Open表中
						bool inopen=false;
						bool inclose =false;
						NightProState *ptemp;
						//检查是否在Open表之中
						i=Openlist.GetCount();
						if(i==0)
							inopen=false;
						else
						{
							for(k=0;k<i;k++)
							{
								ptemp=(NightProState *)Openlist.GetAt(Openlist.FindIndex(k));
								if(Compare(newstate,ptemp)==true)
								{
									inopen=true;
									if(ptemp->curdistance>newstate->curdistance)
										CopyNightNum(newstate,ptemp);
									break;
								}
							}
						}
						//检查是否在Result表之中
						i=ResultList.GetCount();
						if(i==0)
							inclose=false;
						else
						{
							for(k=0;k<i;k++)
							{
								ptemp=(NightProState *)ResultList.GetAt(ResultList.FindIndex(k));
								if(Compare(newstate,ptemp)==true)
								{
									inclose=true;
									break;
								}
							}
						}
						if((inopen==false)&&(inclose==false))
							Openlist.AddHead(newstate);
						
						else
						{
							//找到目标节点
							NightProState *newstate0;
							ResultList.AddHead((void *)newstate);
							newstate=newstate->laststate;
							while(newstate!=pstart)
							{
								newstate0=(NightProState *)malloc(sizeof(NightProState));
								CopyNightNum(newstate,newstate0);
								ResultList.AddHead(newstate0);
								newstate=newstate->laststate;
							}
							newstate0=(NightProState *)malloc(sizeof(NightProState));
							CopyNightNum(newstate,newstate0);
							ResultList.AddHead(newstate0);
							return true;
						}
					}
					else
					{
						free(newstate);
					}
					newstate=(NightProState *)malloc(sizeof(NightProState));
				}
					//下移
					if((MoveDown(pmin,newstate)==true) && (newstate->curdistance<=MAXDEPTH))
					{
						if((Compare(newstate,&ObjState)==false))
						{
							//如果不是目标节点，看是否可以加入到Open表中
							bool inopen=false;
							bool inclose =false;
							NightProState *ptemp;
							//检查是否在Open表之中
							i=Openlist.GetCount();
							if(i==0)
								inopen=false;
							else
							{
								for(k=0;k<i;k++)
								{
									ptemp=(NightProState *)Openlist.GetAt(Openlist.FindIndex(k));
									if(Compare(newstate,ptemp)==true)
									{
										inopen=true;
										if(ptemp->curdistance>newstate->curdistance)
											CopyNightNum(newstate,ptemp);
										break;
									}
								}
							}
							//检查是否在Result表之中
							i=ResultList.GetCount();
							if(i==0)
								inclose=false;
							else
							{
								for(k=0;k<i;k++)
								{
									ptemp=(NightProState *)ResultList.GetAt(ResultList.FindIndex(k));
									if(Compare(newstate,ptemp)==true)
									{
										inclose=true;
										break;
									}
								}
							}
							if((inopen==false)&&(inclose==false))
								Openlist.AddHead(newstate);
							
							else
							{
								//找到目标节点
								NightProState *newstate0;
								ResultList.AddHead((void *)newstate);
								newstate=newstate->laststate;
								while(newstate!=pstart)
								{
									newstate0=(NightProState *)malloc(sizeof(NightProState));
									CopyNightNum(newstate,newstate0);
									ResultList.AddHead(newstate0);
									newstate=newstate->laststate;
								}
								newstate0=(NightProState *)malloc(sizeof(NightProState));
								CopyNightNum(newstate,newstate0);
								ResultList.AddHead(newstate0);
								return true;
							}
						}
						else
						{
							free(newstate);
						}
						newstate=(NightProState *)malloc(sizeof(NightProState));
						
					}
					

}

}

int CEIGHTNUMS::CompareFunction(NightProState *cur, NightProState *dest)
{
    int xcur[9],ycur[9],ydest[9],xdest[9];
	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;
}

bool CEIGHTNUMS::Compare(NightProState *cur1, NightProState *cur2)
{
  for(int i=0;i<3;i++)
  {
	  for(int j=0;j<3;j++)
	  {
		  if(cur1->state[i][j]!=cur2->state[i][j])
			  return false;
	  }
  }
  return true;

}

bool CEIGHTNUMS::MoveDown(NightProState *cur, NightProState *obj)
{
   int x,y;
  int curx,cury;
  for(x=0;x<3;x++)
  {
       for(y=0;y<3;y++)
	   {
	    if(cur->state[x][y]==0)
		{
		 curx=x;
	     cury=y;
		}
	   }
  }
  if(curx==2)
	  return false;
  for(int i=0;i<3;i++)
  {
	  for(int j=0;j<3;j++)
	  {
		  obj->state[i][j]=cur->state[i][j];
	  }
  }
  obj->state[curx][cury]=cur->state[curx+1][cury];
  obj->state[curx+1][cury]=0;
  obj->curdistance=cur->curdistance+1;
  obj->laststate=cur;
  obj->nextstate=NULL;
  return true;

}

bool CEIGHTNUMS::MoveUp(NightProState *cur, NightProState *obj)
{
int x,y;
    int curx,cury;
    for(x=0;x<3;x++)
  {
       for(y=0;y<3;y++)
	 {
	   if(cur->state[x][y]==0)
	   {
		 curx=x;
	     cury=y;
	   }
	 }
  }
  if(curx==0)
	  return false;
  for(int i=0;i<3;i++)
  {
	  for(int j=0;j<3;j++)
	  {
		  obj->state[i][j]=cur->state[i][j];
	  }
  }
  obj->state[curx][cury]=cur->state[curx-1][cury];
  obj->state[curx-1][cury]=0;
  obj->curdistance=cur->curdistance+1;
  obj->laststate=cur;
  obj->nextstate=NULL;
  return true;

}

bool CEIGHTNUMS::MoveRight(NightProState *cur, NightProState *obj)
{
int x,y;
  int curx,cury;
  for(x=0;x<3;x++)
  {
     for(y=0;y<3;y++)
	 {
	 if(cur->state[x][y]==0)
	 {
		 curx=x;
	     cury=y;
	 }
	 }
  }
  if(cury==2)
	  return false;
  for(int i=0;i<3;i++)
  {
	  for(int j=0;j<3;j++)
	  {
		  obj->state[i][j]=cur->state[i][j];
	  }
  }
  obj->state[curx][cury]=cur->state[curx][cury+1];
  obj->state[curx][cury+1]=0;
  obj->curdistance=cur->curdistance+1;
  obj->laststate=cur;
  obj->nextstate=NULL;
  return true;
}

bool CEIGHTNUMS::MoveLeft(NightProState *cur, NightProState *obj)
{
  int x,y;
  int curx,cury;
  for(x=0;x<3;x++)
  {
     for(y=0;y<3;y++)
	 {
	 if(cur->state[x][y]==0)
	 {
		 curx=x;
	     cury=y;
	 }
	 }
  }
  if(cury==0)
	  return false;
  for(int i=0;i<3;i++)
  {
	  for(int j=0;j<3;j++)
	  {
		  obj->state[i][j]=cur->state[i][j];
	  }
  }
  obj->state[curx][cury]=cur->state[curx][cury-1];
  obj->state[curx][cury]=0;
  obj->curdistance=cur->curdistance+1;
  obj->laststate=cur;
  obj->nextstate=NULL;
  return true;

}

void CEIGHTNUMS::OnNextstep() 
{
	// TODO: Add your control notification handler code here
	
}