ninegird.cpp

八数码问题的C++程序代码。八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式

// NineGird.cpp: implementation of the CNineGird class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "NineGrid.h"
#include "NineGird.h"

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

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

CNineGird::CNineGird()
{
	bIsRunning = FALSE;
}

CNineGird::~CNineGird()
{
	//清空求解路径表
	if(!m_PathList.IsEmpty())
	{
		Node *pNode;
		POSITION posList = m_PathList.GetHeadPosition();
		POSITION posOldList =  posList;
		while(posList)
		{
			pNode = (Node *)m_PathList.GetNext(posList);
			m_PathList.RemoveAt(posOldList);
			delete pNode;
			posOldList = posList;
		}
	}
}

void CNineGird::CreateIniStatus(void)
{
	vector<int> vs;
	int i;
	for (i = 1 ; i < 9 ; i ++)
		vs.push_back(i);
	vs.push_back(0);
	random_shuffle(vs.begin(), vs.end()); 
	random_shuffle(vs.begin(), vs.end()); 
	for ( i = 0 ; i < 9 ; i ++)
	{
		m_iIniChess[i] = vs[i];
	}
	
	if (!EstimateUncoil(m_iIniChess))
	{
		unsigned char array[9] = {1,2,3,8,0,4,7,6,5};
		memcpy(m_iTargetChess , array , 9);
	}
	else
	{
		unsigned char array[9] = {1,2,3,4,5,6,7,8,0};
		memcpy(m_iTargetChess , array , 9);
	}
}

bool CNineGird::EstimateUncoil(unsigned char *array)
{
	int sum = 0;
	for ( int i = 0 ; i < 8 ; i ++)
	{
		for ( int j = 0 ; j < 9 ; j ++)
		{
			if (array[j] != 0)
			{
				if (array[j] == i +1 )
					break;
				if (array[j] < i + 1)
					sum++;
			}
		}
	}
	if (sum % 2 == 0)
		return true;
	else
		return false;
}

//压缩到字
inline void CNineGird::ArrayToDword(unsigned char *array , DWORD& data)
{
	unsigned char night = 0;
	for ( int i = 0 ; i < 9 ; i ++)
	{
		if (array[i] == 8)
		{
			night = (unsigned char)i;
			break;
		}
	}
	
	array[night] = 0;
	data = 0;
	data =	 (DWORD)((DWORD)array[0] << 29 | (DWORD)array[1] << 26 | 
					 (DWORD)array[2] << 23 | (DWORD)array[3] << 20 | 
					 (DWORD)array[4] << 17 | (DWORD)array[5] << 14 | 
					 (DWORD)array[6] << 11 | (DWORD)array[7] <<  8 | 
					 (DWORD)array[8] <<  5 | night);
	
	array[night] = 8;
}

/*inline*/ void CNineGird::DwordToArray(DWORD data , unsigned char *array)
{
	unsigned char chtem;
	for ( int i = 0 ; i < 9 ; i ++)
	{
		chtem = (unsigned char)(data >> (32 - (i + 1) * 3) & 0x00000007);
		array[i] = chtem;
	}
	chtem = (unsigned char)(data & 0x0000001F);
	array[chtem] = 8;
}

inline bool CNineGird::MoveChess(unsigned char *array , int way)
{
	int zero , chang;
	bool moveok = false;
	for ( zero = 0 ; zero < 9 ; zero ++)
	{
		if (array[zero] == 0)
			break;
	}
	POINT pnt;
	pnt.x = zero % 3;
	pnt.y = int(zero / 3);
	switch(way)
	{
	case 0 : //down
		if (pnt.y + 1 < 3)
		{
			chang = (pnt.y + 1) * 3 + pnt.x ;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 1 : //up
		if (pnt.y - 1 > -1)
		{
			chang = (pnt.y - 1) * 3 + pnt.x ;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 2 : //right
		if (pnt.x + 1 < 3)
		{
			chang = pnt.y * 3 + pnt.x + 1;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 3 : //left
		if (pnt.x - 1 > -1)
		{
			chang = pnt.y * 3 + pnt.x - 1;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	}
	
	return moveok;
}

//与目标状态比较
inline bool CNineGird::CompareTargetChess(unsigned char *current,unsigned char *target)
{
	DWORD temp1 ,temp2;
	ArrayToDword(current , temp1);
	ArrayToDword(target , temp2);
	if (temp1 == temp2)
		return true;
	else
		return false;
}

//与目标状态比较
inline bool CNineGird::CompareTargetChess(DWORD dwCurrent,unsigned char *target)
{
	DWORD temp2;
	ArrayToDword(target , temp2);
	if (dwCurrent == temp2)
		return true;
	else
		return false;
}

//在OPEN和CLOSED中查找目标节点,dwNode为压缩后的节点数据
inline bool CNineGird::FindNode_InOpenClosedList(DWORD dwNode)
{
	bool bFindOpen = false;
	bool bFindClosed = false;

	//OPEN表中寻找
	Node *pOpenNode = NULL;
	POSITION posList = m_OpenList.GetHeadPosition();
	for (int i = 0; i < m_OpenList.GetCount(); i++)
	{
		pOpenNode = (Node *)m_OpenList.GetNext(posList);
		if(pOpenNode->dwStatus == dwNode)
		{
			bFindOpen = true;
			return true;
		}
	}
	
	//在CLOSED表中寻找
	if(bFindOpen == false)
	{
		Node *pClosedNode = NULL;
		posList = m_ClosedList.GetHeadPosition();
		for (i = 0; i < m_ClosedList.GetCount(); i++)
		{
			pClosedNode = (Node *)m_ClosedList.GetNext(posList);
			if(pClosedNode->dwStatus == dwNode)
			{
				bFindClosed = true;
				return true;
			}
		}
	}

	return false;
}

//当前节点在父辈节点中是否出现
inline bool CNineGird::FindNode_IsParents(DWORD dwStatus,Node *pNode)
{
	Node *pCurrent = pNode;
	Node *pParents = pNode->pParents;

	bool bflag = false;

	while(pParents != NULL)
	{
		pCurrent = pCurrent->pParents;
		if(pCurrent->dwStatus == dwStatus)
		{
			bflag = true;
			break;
		}
		
		pParents = pCurrent->pParents;
	}

	return bflag;
}

//搜索算法
BOOL CNineGird::SearchTargetChess(unsigned char *ini,unsigned char *target,HWND hwnd)
{
	BOOL bFlag = FALSE;

	//清空OPEN表
	if(!m_OpenList.IsEmpty())
	{
		Node *pOpenNode;
		POSITION posList = m_OpenList.GetHeadPosition();
		POSITION posOldList =  posList;
		while(posList)
		{
			pOpenNode = (Node *)m_OpenList.GetNext(posList);
			m_OpenList.RemoveAt(posOldList);
			delete pOpenNode;
			posOldList = posList;
		}
	}

	//清CLOSED表
	if(!m_ClosedList.IsEmpty())
	{
		Node *pClosedNode;
		POSITION posList = m_ClosedList.GetHeadPosition();
		POSITION posOldList =  posList;
		while(posList)
		{
			pClosedNode = (Node *)m_ClosedList.GetNext(posList);
			m_ClosedList.RemoveAt(posOldList);
			delete pClosedNode;
			posOldList = posList;
		}
	}

	//清空求解路径表
	if(!m_PathList.IsEmpty())
	{
		Node *pNode;
		POSITION posList = m_PathList.GetHeadPosition();
		POSITION posOldList =  posList;
		while(posList)
		{
			pNode = (Node *)m_PathList.GetNext(posList);
			m_PathList.RemoveAt(posOldList);
			delete pNode;
			posOldList = posList;
		}
	}
	
	//把初始节点S0放入OPEN表中
	Node *pOpenNode = new Node();
	ArrayToDword(ini,pOpenNode->dwStatus);//压缩
	pOpenNode->pParents = NULL;
	m_OpenList.AddTail((CObject *)pOpenNode);

	DWORD dwCloseNodeNO = 0;
	DWORD dwCaluStep = 0;
	Node *pClosedCurrentNode = NULL;//CLOSED表中的当前节点
	DWORD dwTarget;//目标压缩字
	ArrayToDword(this->m_iTargetChess , dwTarget);
	unsigned char aiChess[9];//状态数组
	unsigned char aiTemp[9];//状态数组
	while(!m_OpenList.IsEmpty())//判断OPEN表是否为空
	{
		Node *pOpenNode = (Node *)m_OpenList.GetHead();
		POSITION posList = m_OpenList.GetHeadPosition();
		m_OpenList.RemoveAt(posList);//移除OPEN表队首元素

		pOpenNode->dwNo = dwCloseNodeNO++;
		m_ClosedList.AddTail((CObject *)pOpenNode);//添加刚才OPEN表的元素到CLOSED表中

		pClosedCurrentNode = pOpenNode;
		//if(CompareTargetChess(pClosedCurrentNode->dwStatus,this->m_iTargetChess))//比较当前CLOSE表节点是否为目标节点
		if(dwTarget == pClosedCurrentNode->dwStatus)//比较当前CLOSE表节点是否为目标节点
		{
			bFlag = TRUE;//置找到标志
			break;//退出循环
		}
		else//未找到扩展运算,算子运算
		{
			DwordToArray(pClosedCurrentNode->dwStatus,aiChess);//当前状态数据解压到数组
			bool bMove = false;
			for(int i=0;i<4;i++)//空格上下左右移动
			{
				bMove = false;
				memcpy(aiTemp , aiChess , 9);
				if(MoveChess(aiTemp,i))//能合法移动
				{
					DWORD dwStatus;
					ArrayToDword(aiTemp,dwStatus);//压缩数组
					if(!FindNode_InOpenClosedList(dwStatus))//扩展的状态在OPEN和CLOESED表中均未发现,添加到OPEN表尾部(宽度优先)
					//if(!FindNode_IsParents(dwStatus,pClosedCurrentNode))
					{
						Node *pOpenNode = new Node();
						ArrayToDword(aiTemp,pOpenNode->dwStatus);//压缩
						pOpenNode->pParents = pClosedCurrentNode;//设置父指针
						m_OpenList.AddTail((CObject *)pOpenNode);
						
						//debug
						/*
						unsigned char ai[9];
						DwordToArray(pOpenNode->dwStatus,ai);
						TRACE("%d %d %d %d %d %d %d %d %d\n",
							ai[0],ai[1],ai[2],ai[3],ai[4],
							ai[5],ai[6],ai[7],ai[8]);*/
						TRACE("步数:%d\n",dwCloseNodeNO);
						//debug end
						dwCaluStep ++;
						PostMessage(hwnd, WM_UPDATAMSG, 0, dwCaluStep);
						Sleep(2);
					}
				}
			}
		}

	}

	if(bFlag && pClosedCurrentNode != NULL)//问题有解情况,把解路径存入m_PathList表中
	{
		Node *pCurrent = pClosedCurrentNode;
		Node *pParents = pClosedCurrentNode->pParents;
		
		Node *pPathNode = new Node();
		pPathNode->dwNo = pCurrent->dwNo;
		pPathNode->dwStatus = pCurrent->dwStatus;
		pPathNode->pParents = NULL;
		m_PathList.AddHead((CObject *)pPathNode);

		TRACE("路径输出开始\n");
		while(pParents != NULL)
		{
			pCurrent = pCurrent->pParents;
			pPathNode = new Node();
			pPathNode->dwNo = pCurrent->dwNo;
			pPathNode->dwStatus = pCurrent->dwStatus;
			pPathNode->pParents = NULL;
			m_PathList.AddHead((CObject *)pPathNode);

			//debug
			unsigned char ai[9];
			DwordToArray(pCurrent->dwStatus,ai);
			TRACE("%d %d %d %d %d %d %d %d %d\n",
			ai[0],ai[1],ai[2],ai[3],ai[4],
			ai[5],ai[6],ai[7],ai[8]);
			//debug end

			pParents = pCurrent->pParents;
		}
		PostMessage(hwnd, WM_UPDATAMSG, 1, dwCaluStep);
	}

	//清空OPEN和CLOSED,释放内存
	//清空OPEN表
	if(!m_OpenList.IsEmpty())
	{
		Node *pOpenNode;
		POSITION posList = m_OpenList.GetHeadPosition();
		POSITION posOldList =  posList;
		while(posList)
		{
			pOpenNode = (Node *)m_OpenList.GetNext(posList);
			m_OpenList.RemoveAt(posOldList);
			delete pOpenNode;
			posOldList = posList;
		}
	}
	//清CLOSED表
	if(!m_ClosedList.IsEmpty())
	{
		Node *pClosedNode;
		POSITION posList = m_ClosedList.GetHeadPosition();
		POSITION posOldList =  posList;
		while(posList)
		{
			pClosedNode = (Node *)m_ClosedList.GetNext(posList);
			m_ClosedList.RemoveAt(posOldList);
			delete pClosedNode;
			posOldList = posList;
		}
	}

	return bFlag;
}