ninegird.cpp

人工智能中经典的九宫问题（八数码问题）

//
// Created by ZhaoHongWei 2004-12-6
// Feel free to use this code in any way you want.
#include "stdafx.h"
#include "NineGird.h"

CNineGird::CNineGird()
{
	m_pPathList = NULL;
	m_pPlaceList = NULL;
	m_pScanbuf = NULL;
	m_iPathsize = 0;
	m_iTime = 0;
	m_bAutoRun = false;
	Reset();
}

CNineGird::~CNineGird()
{
	if (m_pPathList != NULL)
	{
		delete[] m_pPathList;
	}

	if (m_pScanbuf != NULL)
	{
		delete[] m_pScanbuf;
	}
}

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;
}

bool CNineGird::ComputeFeel()
{
	unsigned char *array = m_iChess;
	UINT i;
	const int MAXSIZE = 362880;
	unsigned char temparray[9];
	
	DWORD target , fountain , parent , parentID = 0 , child = 1;
	ArrayToDword(m_iTargetChess , target);
	ArrayToDword(array , fountain);

	if (fountain == target)
	{
		return false;
	}

	if (m_pScanbuf != NULL)
	{
		delete[] m_pScanbuf;
	}
	m_pScanbuf = new Scanbuf[MAXSIZE];
	AddTree(fountain ,m_pPlaceList);
	m_pScanbuf[ 0 ].Place = fountain;
	m_pScanbuf[ 0 ].ScanID = -1;

	clock_t tim = clock();

	while(parentID < MAXSIZE && child < MAXSIZE)
	{
		parent = m_pScanbuf[parentID].Place;
		for ( i = 0 ; i < 4 ; i ++)
		{
			DwordToArray(parent , temparray);
			if (MoveChess(temparray,i))
			{
				ArrayToDword(temparray , fountain);
				if (AddTree(fountain, m_pPlaceList))
				{
					m_pScanbuf[ child ].Place = fountain;
					m_pScanbuf[ child ].ScanID = parentID;
					if (fountain == target)
					{
						m_iTime = clock() - tim;
						GetPath(child);
						FreeTree(m_pPlaceList);
						delete[] m_pScanbuf;
						m_pScanbuf = NULL;
						return true;
					}
					child ++;
				}
			}
		} // for i
		parentID++;
	}

	m_iTime = clock() - tim;

	FreeTree(m_pPlaceList);
	delete[] m_pScanbuf;
	m_pScanbuf = NULL;
	return false;
}

inline bool CNineGird::AddTree(DWORD place , PlaceList*& parent)
{
	if (parent == NULL)
	{
		parent = new PlaceList();
		parent->Left = parent->Right = NULL;
		parent->Place = place;
		return true;
	}
	if (parent->Place == place)
	{
		return false;
	}
	if (parent->Place > place)
	{
		return AddTree(place , parent->Right);
	}
	return AddTree(place , parent->Left);
}

void CNineGird::FreeTree(PlaceList*& parent)
{
	if (parent != NULL)
	{
		if ( parent->Left != NULL)
			FreeTree(parent->Left);
		if ( parent->Right != NULL)
			FreeTree(parent->Right);
		delete parent;
		parent = NULL;
	}
}

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 : //up
		if (pnt.y + 1 < 3)
		{
			chang = (pnt.y + 1) * 3 + pnt.x ;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 1 : //down
		if (pnt.y - 1 > -1)
		{
			chang = (pnt.y - 1) * 3 + pnt.x ;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 2 : //left
		if (pnt.x + 1 < 3)
		{
			chang = pnt.y * 3 + pnt.x + 1;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 3 : //right
		if (pnt.x - 1 > -1)
		{
			chang = pnt.y * 3 + pnt.x - 1;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	}
	if (moveok && !m_bAutoRun)
	{
		m_iStepCount ++ ;
		
		DWORD temp1 ,temp2;
		ArrayToDword(array , temp1);
		ArrayToDword(m_iTargetChess , temp2);
		if (temp1 == temp2)
		{
			MessageBox(NULL , "你真聪明这么快就搞定了!" , "^_^" , 0);		
		}
	}
	return moveok;
}

bool CNineGird::EstimateUncoil(unsigned char *array)
{
	int sun = 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)
					sun++;
			}
		}
	}
	if (sun % 2 == 0)
		return true;
	else
		return false;
}

void CNineGird::GetPath(UINT depth)
{
	int now = 0 , maxpos = 100 ;
	UINT parentid;
	if (m_pPathList != NULL)
	{
		delete[] m_pPathList;
	}
	m_pPathList = new PathList[maxpos];
	parentid = m_pScanbuf[depth].ScanID;
	
	DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);
	
	while(parentid != -1)
	{
		if (now == maxpos)
		{
			maxpos += 10;
			PathList * temlist = new PathList[maxpos];
			memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
			delete[] m_pPathList;
			m_pPathList = temlist;
		}
		DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);
		parentid = m_pScanbuf[parentid].ScanID;
	}
	m_iPathsize = now;
}

unsigned __stdcall MoveChessThread(LPVOID pParam)
{
	CNineGird * pGird = (CNineGird *)pParam;
	RECT rect;
	pGird->m_iStepCount = 0;
	::GetClientRect(pGird->m_hClientWin , &rect);
	for ( int i = pGird->m_iPathsize ; i > 0 ; i --)
	{
		memcpy(pGird->m_iChess , pGird->m_pPathList[i].Path , 9);
		pGird->m_iStepCount ++;
		InvalidateRect( pGird->m_hClientWin , &rect , false);
		Sleep(300);
	}
	char msg[100];
	sprintf(msg , "^_^ ! 搞定了!\r\n计算步骤用时%d毫秒" , pGird->m_iTime);
	MessageBox(NULL , msg , "~_~" , 0);
	pGird->m_bAutoRun = false;
	return 0L;
}

void CNineGird::ActiveShaw(HWND hWin)
{
	if (m_bAutoRun) return;
	m_bAutoRun = true;
	if (!ComputeFeel()) 
	{
		m_bAutoRun = true;
		return;
	}
	
	m_hClientWin = hWin;
	
	HANDLE hThread;
	unsigned threadID;
	hThread = (HANDLE)_beginthreadex( NULL, 0, &MoveChessThread, this, 0, &threadID );
}

void CNineGird::DrawGird(HDC hDC , RECT clientrect)
{
	int cx = clientrect.right / 2 - 180 ;
	int cy = clientrect.bottom / 2 - 60 ;
	int i , j;

	HBRUSH hgirdbkbrush = ::CreateSolidBrush(RGB(255 , 128 , 64));
	HBRUSH hbutbrush = ::CreateSolidBrush(RGB(0 , 128 , 255));
	HBRUSH oldbrush = (HBRUSH)::SelectObject(hDC , hgirdbkbrush);
	COLORREF oldbkcolor = SetBkColor(hDC , RGB(0 , 128 , 255));
	// Draw fountain gird
	RECT rect;
	for (i = 0 ; i < 3 ; i ++)
	{
		for ( j = 0 ; j < 3 ; j ++)
		{
			SetRect(&rect , 0 , 0 , 40 , 40);
			OffsetRect(&rect , i * 40 + cx, j * 40 + cy);
			Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);
		}
	}
	
	// Draw target gird
	cx = clientrect.right / 2 + 60 ;
	for (i = 0 ; i < 3 ; i ++)
	{
		for ( j = 0 ; j < 3 ; j ++)
		{
			SetRect(&rect , 0 , 0 , 40 , 40);
			OffsetRect(&rect , i * 40 + cx, j * 40 + cy);
			Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);
		}
	}

	SelectObject(hDC , hbutbrush);
	
	// draw step rect
	cx = clientrect.right / 2 - 30 ;
	cy += 10;
	SetRect(&rect , 0 , 0 , 80 , 20);
	OffsetRect(&rect , cx - 10 , cy);
	Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);
	char step[100];
	sprintf(step , "Step: %d" , m_iStepCount);
	rect.top += 2;
	DrawText(hDC ,step , strlen(step) , &rect , DT_CENTER);
	
	// draw reset button
	cx = clientrect.right / 2 - 30 ;
	cy += 40;
	SetRect(&m_rResetButton , 0 , 0 , 80 , 20);
	OffsetRect(&m_rResetButton , cx - 10 , cy);
	Rectangle(hDC , m_rResetButton.left , m_rResetButton.top , m_rResetButton.right , m_rResetButton.bottom);
	char msg[] = "Reset";
	m_rResetButton.top += 2;
	DrawText(hDC ,msg , strlen(msg) , &m_rResetButton , DT_CENTER);
	
	// draw AutoPlay button
	cx = clientrect.right / 2 - 30 ;
	cy += 40;
	SetRect(&m_rAutoButton , 0 , 0 , 80 , 20);
	OffsetRect(&m_rAutoButton , cx - 10 , cy);
	Rectangle(hDC , m_rAutoButton.left , m_rAutoButton.top , m_rAutoButton.right , m_rAutoButton.bottom);
	char msg2[] = "AutoPlay";
	m_rAutoButton.top += 2;
	DrawText(hDC ,msg2 , strlen(msg2) , &m_rAutoButton , DT_CENTER);

	SetBkColor(hDC , oldbkcolor);
	::SelectObject(hDC , oldbrush);
	DeleteObject(hgirdbkbrush);
	DeleteObject(hbutbrush);
}

void CNineGird::DrawChess(HDC hDC , RECT clientrect)
{
	int cx = clientrect.right / 2 - 180 ;
	int cy = clientrect.bottom / 2 - 60 ;

	RECT rect;
	char ch[2];
	int i , j;
	int tcount = 0;
	
	COLORREF oldbkcolor = SetBkColor(hDC , RGB(255 , 128 , 64));
	
	// Draw fountain number
	for ( i = 0 ; i < 3 ; i ++)
	{
		for ( j = 0 ; j < 3 ; j ++)
		{
			int t = m_iChess[tcount++];
			rect.left = j * 40;
			rect.top = i * 40;
			rect.right =  rect.left + 15;
			rect.bottom =  rect.top + 15;
			OffsetRect(&rect , 12 + cx , 12 + cy);
			if (t != 0 )
			{
				ch[0] = t + '0';
				DrawText(hDC , ch , 1 , &rect , DT_CENTER);
			}
			else
			{
				ch[0] = ch[1] = ' ';
				DrawText(hDC , ch , 2 , &rect , DT_CENTER);
			}
		}
	}
	
	// Draw target number
	cx = clientrect.right / 2 + 60 ;
	tcount = 0;
	for ( i = 0 ; i < 3 ; i ++)
	{
		for ( j = 0 ; j < 3 ; j ++)
		{
			int t = m_iTargetChess[tcount++];
			rect.left = j * 40;
			rect.top = i * 40;
			rect.right =  rect.left + 15;
			rect.bottom =  rect.top + 15;
			OffsetRect(&rect , 12 + cx , 12 + cy);
			if (t != 0 )
			{
				ch[0] = t + '0';
				DrawText(hDC , ch , 1 , &rect , DT_CENTER);
			}
			else
			{
				ch[0] = ch[1] = ' ';
				DrawText(hDC , ch , 2 , &rect , DT_CENTER);
			}
		}
	}
	SetBkColor(hDC , oldbkcolor);
}

void CNineGird::Reset()
{
	if(m_bAutoRun) return;
	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_iChess[i] = vs[i];
	}
	
	if (!EstimateUncoil(m_iChess))
	{
		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);
	}

	m_iStepCount = 0;
}

void CNineGird::MoveChess(int way)
{
	MoveChess(m_iChess , way);
}

void CNineGird::OnButton(POINT pnt , HWND hWin)
{
	if (PtInRect(&m_rResetButton , pnt))
	{
		Reset();
	}
	else if (PtInRect(&m_rAutoButton , pnt))
	{
		ActiveShaw(hWin);
	}
}