chessdoc.cpp

解决八数码问题的经典程序。实现了宽带优先算法

// ChessDoc.cpp : implementation of the CChessDoc class
//

#include "stdafx.h"
#include "Chess.h"
#include "string.h"
#include "conio.h"
#include "Datatype.h"

#include "ChessDoc.h"

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

/////////////////////////////////////////////////////////////////////////////
// CChessDoc

IMPLEMENT_DYNCREATE(CChessDoc, CDocument)

BEGIN_MESSAGE_MAP(CChessDoc, CDocument)
	//{{AFX_MSG_MAP(CChessDoc)
	ON_COMMAND(ID_FILE_OPEN, OnFileOpen)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CChessDoc construction/destruction

CChessDoc::CChessDoc()
{
	// TODO: add one-time construction code here
	m_bFileOpen=FALSE;
	m_N=0;
	m_NUM=0;
	m_bBeginDraw=FALSE;
	m_nType=-1;
}

CChessDoc::~CChessDoc()
{
}

BOOL CChessDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}
int CChessDoc::Start2GoalS(const unsigned char *start,const unsigned  char *goal,UINT N,UINT NUM)
{//求各数码当前位置到目标位置的距离之和
	UINT i,j,s;
	for(s=0,i=0;i<NUM;i++)
	{
		if(goal[i]!='0')
		{
			for(j=0;j<NUM && start[j]!=goal[i];j++);
			s+=abs(i/N-j/N)+abs(i%N-j%N);
		}
	}
	return s;
}



/////////////////////////////////////////////////////////////////////////////
// CChessDoc serialization

void CChessDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CChessDoc diagnostics

#ifdef _DEBUG
void CChessDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CChessDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CChessDoc commands

//求当前状态到目标状态的换位数
int CChessDoc::Start2GoalL(unsigned char *start, unsigned char *goal, UINT N, UINT NUM)
{
	UINT i,j,l,m,n,init,data;
	unsigned char temp[16];
	for(i=0;i<NUM;i++) temp[i]=i;
	for(i=0,j=0,l=0;i<NUM && j<NUM;i++,l+=n-1)
	{
		data=init=goal[temp[0]];
		n=0;
		do
		{
			for(j++,n++,m=0;m<NUM-j;m++)
				if(goal[temp[m]]==data) break;
			data=start[temp[m]];
			memcpy(temp+m,temp+m+1,NUM-j-m);
			temp[NUM-j]=0;
		}
		while(init!=data);
	}
	return l;
}

int CChessDoc::Start2GoalZ(unsigned char *start, unsigned char *goal, UINT NUM)
{//当前状态到目标状态未移动的码数
	UINT i,z;
	for(z=0,i=0;i<NUM;i++)
		z+=(start[i]==goal[i])? 1:0;
	return z;
}
int CChessDoc::Start2GoalW(unsigned char *start, unsigned char *goal, UINT NUM)
{//不在位的码数
	UINT i,z;
	for(z=0,i=0;i<NUM;i++)
	{
		if (start[i]=='0') continue;
		z+=(start[i]!=goal[i])? 1:0;
	}
	return z;
}
//测试目标状态是否可以通过当前状态得到
int CChessDoc::Test(unsigned char *start, unsigned char *goal,UINT N,UINT NUM)
{
	int l,s;
	l=Start2GoalL(start,goal,N,NUM);
	s=Start2GoalS(start,goal,N,NUM);
	return ((l+s)%2==0) ? 0  :-1;

}

int CChessDoc::DFS(unsigned char *start, unsigned char *goal)
{
	CPathNode *info,*p,*OpenFirst;
	OpenFirst=NULL;
	unsigned char nextspace;
	int m,n,same,flag=-1;
	//初始化第一个结点
	info=new CPathNode(m_N,0);
	memcpy(info->state,start,m_NUM);
	info->space=strcspn((char*)start,"0");
	info->move='0';
	info->depth=info->rule=0;
	
	info->next=NULL;
	OpenFirst=info;

	m_nGenerate=0;
	m_nSplit=1;
	m_nResult=0;
	flag=1;
	while(_kbhit()==0)
	{
		info=new CPathNode(m_N);
		memcpy(info->state,OpenFirst->state,m_NUM);
		info->space=OpenFirst->space;
		info->depth=OpenFirst->depth;
		info->rule=OpenFirst->rule;
		OpenFirst->rule++;//下一规则
		
		if(OpenFirst->rule>=(UINT)4)
			m_nSplit++;

		if(info->rule>=(UINT)4 || info->depth>m_nDepth)
		{
			delete info;
			//////////////////////
			if(OpenFirst)
			{
				OpenFirst=(p=OpenFirst)->next;
				delete p;
			}
			if(OpenFirst==NULL) 
				return flag;
			continue;
		}
		
	
		nextspace=info->space+(2*info->rule-3)/2*m_N+
			1/(2*info->rule-3);
		if(nextspace<0 || nextspace>m_NUM-1 ||
			(info->space%m_N==0 && info->rule==1) ||
			(info->space%m_N==m_N-1 && info->rule==2))
		{//空格出界
			delete info;
			continue;
		}

		info->move=info->state[info->space]=info->state[nextspace];

		info->state[nextspace]='0';//填充当前结点
		m=Start2GoalS(info->state,goal,m_N,m_NUM);
		n=m_nDepth-info->depth;

		for(p=OpenFirst,same=0;p;p=p->next)
		{
			if(m>n|| memcmp(p->state,info->state,m_NUM)==0)
			{
				same=-1;
				delete info;
				break;
			}
		}
		if(same==0)
		{
			info->space=nextspace;
			info->depth++;
			info->rule=0;
			//将该结点加入链表
			if(!OpenFirst)
			{
				info->next=NULL;
				OpenFirst=info;
			}
			else
			{
				info->next=OpenFirst;
				OpenFirst=info;
			}
			m_nGenerate++;
		
			if(memcmp(info->state,goal,m_NUM)==0)
			{//若当前结点和目标状态相同
				m_nResult=(m_nDepth>info->depth)? 1: m_nResult+1;
				if(m_nResult>MAXRESULT)
				{
					AfxMessageBox("结果数目超出缓存空间");
					flag=-2;
					break;
				}
				m_nDepth=info->depth;
				CResult *res=&m_Result[m_nResult-1];
				if(res->depth!=0)
				{
					delete[] res->moves;
					delete[] res->rules;
				}
				res->moves=new unsigned char[OpenFirst->depth];
				res->rules=new unsigned char[OpenFirst->depth];

			
				res->generate=m_nGenerate;
				res->split=m_nSplit;
				res->depth=OpenFirst->depth;
				

				for(m=info->depth-1,p=OpenFirst;p&& p->move!='0';p=p->next)
				{
					res->moves[m]= p->move;

					res->rules[m]=FindRule(p->next->state,p->move,p->next->space);
					m--;
				}

				flag=0;
			}
		}
	}

}

void CChessDoc::IniVar()
{
	m_nDepth=0;
	m_nGenerate=0;
	m_nResult=0;
	m_nSplit=0;

}

int CChessDoc::SearchDFS()
{
	int p1,p2,p3,exp;
	int exp_max=m_nDepth;

	p1=Start2GoalS(m_strStart,m_strEnd,m_N,m_NUM);
	p2=Start2GoalL(m_strStart,m_strEnd,m_N,m_NUM);
	   
	p3=Start2GoalZ(m_strStart,m_strEnd,m_NUM);
	exp=p1+p2+2*p3;
	if((exp+p2)%2!=0) exp--;
	for(;_kbhit()==0 && exp<exp_max;exp+=2)
	{
		m_nDepth=exp;
		m_nResult=0;
		if(DFS(m_strStart,m_strEnd)==0)
		{
			break;
		}
	}
	
	if (exp<200) return 0;
	else
		return -1;


}

int CChessDoc::FindRule(unsigned char *state, unsigned char ch, int space)
{
	UINT nextspace;
	for(int i=0;i<4;i++)
	{
		nextspace=space+(2*i-3)/2*m_N+1/(2*i-3);
		if(nextspace<0 || nextspace>m_NUM-1 ||
			(space%m_N==0 && i==1) ||
			(space%m_N==m_N-1 && i==2))
		{//空格出界
			continue;
		}
		if(state[nextspace]==ch) return i;
	}
}

int CChessDoc::BFS(unsigned char *start, unsigned char *goal)
{
	CPathNode *info,*p,*OpenFirst,*OpenLast,*CloseFirst;
	UINT nextspace;
	int m,n,i,same,flag,Generate,Split;
	
	//初始化第一个节点
	info=new CPathNode(m_N);
	memcpy(info->state,start,m_NUM);
	info->space=strcspn((char*)start,"0");
	info->depth=0;
	info->move='0';
	info->rule=0;
	info->next=info->parent=NULL;
	//初始化队列
	OpenFirst=OpenLast=info;
	CloseFirst=NULL;
	Generate=0;
	Split=0;
	flag=1;
	while(_kbhit()==0)
	{
		if(!OpenFirst || OpenFirst->depth>m_nDepth)
		{
			flag=-1;
			goto Exit_Label;
		}
		//扩展当前队列
		int splitFlag=0;
		for(i=0;i<4;i++)
		{
			if(OpenFirst->depth==m_nDepth) break;
			
			info= new CPathNode(m_N);
			info->depth=OpenFirst->depth +1;
			memcpy(info->state,OpenFirst->state,m_NUM);
			info->space=OpenFirst->space;
			info->rule=i;
			
			nextspace=info->space+(2*info->rule-3)/2*m_N+
			1/(2*info->rule-3);
			if(nextspace<0 || nextspace>m_NUM-1 ||
				(info->space%m_N==0 && info->rule==1) ||
				(info->space%m_N==m_N-1 && info->rule==2))
			{//空格出界
				delete info;
				continue;
			}
			info->move=info->state[info->space]=info->state[nextspace];
			info->state[nextspace]='0';

			m=Start2GoalS(info->state,goal,m_N,m_NUM);
			n=m_nDepth-info->depth;

			//当前结点和以前的结点是否有相同
			same=0;
			for(p=OpenFirst;p;p=p->next)
			{
				if(m>n||memcmp(p->state,info->state,m_NUM)==0)
				{
					same=-1;
					delete info;
					break;
				}
			}
			if(same==0)
				for(p=CloseFirst;p;p=p->next)
				{
					if(memcmp(p->state,info->state,m_NUM)==0)
					{
						same=-1;
						delete info;
						break;
					}
				}

			if(same==0)
			{
				//插入队列
				info->space=nextspace;
				info->next=NULL;
				info->parent=OpenFirst;

				OpenLast->next=info;
				OpenLast=info;
				Generate++;
				splitFlag=1;
			}
		}//end for
		Split+=splitFlag;

		//若当前结点和目标状态相同
		if(memcmp(OpenFirst->state,goal,m_NUM)==0)
		{
			m_nResult=(m_nDepth>OpenFirst->depth)? 1: m_nResult+1;
			m_nDepth=OpenFirst->depth;
			//检查m_Resutl
			CResult *res=&m_Result[m_nResult-1];
			if(res->depth!=0)
			{
				delete[] res->moves;
				delete[] res->rules;
			}
			res->moves=new unsigned char[OpenFirst->depth];
			res->rules=new unsigned char[OpenFirst->depth];

			res->generate=Generate;
			res->split=Split;
			res->depth=OpenFirst->depth;

			for(p=OpenFirst,i=1;p->move!='0';p=p->parent,i++)
			{
				res->moves[res->depth-i]=p->move;
				res->rules[res->depth-i]=p->rule;
			}
			flag=0;
		}//end if
		//修改ＯＰＥＮ表和ＣＬＯＳＥ表
		info=OpenFirst;
		OpenFirst=OpenFirst->next;
		info->next=NULL;
		if(CloseFirst==NULL)
		{
			CloseFirst=info;
		}
		else
		{
			info->next=CloseFirst;
			CloseFirst=info;
		}
	}//end while
Exit_Label:
	//册除open表和close表
	p=OpenFirst;
	while(p)
	{
		OpenFirst=OpenFirst->next;
		delete p;
		p=OpenFirst;
	}

	p=CloseFirst;
	while(p)
	{
		CloseFirst=CloseFirst->next;
		delete p;
		p=CloseFirst;
	}

	return flag;
}

//S3(),S4()棋牌计分

int CChessDoc::Location(unsigned char *goal, unsigned char ch,UINT NUM)
{
	UINT j;
	for(j=0;j<m_NUM;j++)
		if (goal[j]==ch) break;
	return j;

}

int CChessDoc::Start2GoalPS(unsigned char *start, unsigned char *goal,UINT N,UINT NUM)
{
	UINT s=0;
	UINT i,j;
	for(i=0;i<NUM;i++)
	{
		j=Location(goal,start[i],NUM);
		if(N==3 && i==4)
		{
			if (start[i]!='0') s++;
		}
		else if((N==4) && (i==5 || i==6 || i==9 || i==10))
		{
			if (start[i]!='0') s++;
		}
		else if( i%N==N-1)
		{
			if (j%N!=N-1) s+=2;
		}
		else
		{
			if((j%N==N-1) || (start[i+1]!=goal[j+1])) s+=2;
		}
	}
	return s;
}

void CChessDoc::SortOpen(CPathNode **pHead)
{
	CPathNode *first,*last,*p,*q,*s,*head;
	first=NULL;
	head=*pHead;
	while(head)
	{
		s=head;		p=head;		q=NULL;
		while(p->next)
		{
			if(p->next->weight<s->weight)
			{
				s=p->next;
				q=p;
			}
			p=p->next;