gusucode.com > 马走日棋盘搜索算法C++源码程序 > 马走日棋盘搜索算法/ChessDisplay/ChessDisplay/ChessCalculator.cpp

    //###########################################################################
//ChessCalculator.cpp: implementation of the CChessCalculator class.
//###########################################################################
#include "stdafx.h"
#include "ChessDisplay.h"
#include "ChessCalculator.h"

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

//###########################################################################
//功能  :
//          设置默认的搜索环境
//###########################################################################
CChessCalculator::CChessCalculator()
{
	m_curLoc.x = 3 ; 
	m_curLoc.y = 3 ;
	m_width    = 5;
	m_height   = 5;
	m_index    = 0;
	m_complex  = 0;

	m_start    = false;
	m_result   = false;
	m_end      = false;
	m_nextTime = false;
	m_showDelay= false;
};
//###########################################################################
//功能  :
//          释放搜索环境中动态分配的空间
//###########################################################################
CChessCalculator::~CChessCalculator()
{
	if( m_start )
	{
		for( int i = 0 ; i < m_height ; i++ )
			delete[] m_chessTable[i];
		delete m_chessTable;
		delete m_recordTable;
	}
}
//###########################################################################
//功能  :
//          设置搜索的起始位置
//参数  :   
//          locOnX    :   在高度上的位置
//          locOnY    :   在宽度上的位置
//###########################################################################
void CChessCalculator::SetStartLocation( int locOnX , int locOnY )//设置棋子的起始位置;
{ 
	m_curLoc.x = locOnX;
	m_curLoc.y = locOnY;
}
//###########################################################################
//功能  :
//          设置棋盘的大小
//参数  :
//          width   :   棋盘宽度
//          height  :   棋盘高度
//###########################################################################
void CChessCalculator::SetSize( int width , int height )//设置棋盘的大小;
{
	m_width  = width ; 
	m_height = height;
}
//###########################################################################
//功能  :
//          初始化搜索环境, 启动搜索过程
//###########################################################################
void  CChessCalculator::StartSearch()
{
	m_index    = 0;
	m_complex  = 0;

	m_start    = false;
	m_result   = false;
	m_end      = false;
	m_showDelay= false;
	
	if( m_nextTime )
	{
		for( int i = 0 ; i < m_saveHeight ; i++ )
			delete[] m_chessTable[i];
		delete m_chessTable;

		delete[] m_recordTable;
	}

	m_nextTime = true;
	m_saveWidth = m_width;
	m_saveHeight= m_height;

	//初始化棋盘表;
	m_chessTable = new int*[m_height];
	for( int i = 0 ; i < m_height ; i++ )
	{
		m_chessTable[ i ] = new int[m_width];
		for( int j = 0 ; j < m_width ; j++ )
			m_chessTable[i][j] = 0;
	}
	
	//初始化走棋记录表;
	m_recordTable = new Location[m_width * m_height];
	for( i = 0 ; i < m_width* m_height ; i++ )
	{
		m_recordTable[i].x = 0;
		m_recordTable[i].y = 0;
	}
	
	//记录表记录位置;
	m_index  = 0;
	m_start  = true;
	m_result = Search( m_curLoc );
	m_end    = true;

	//写入文件;
	CFile  recordFile;
	CString fileName = _T("C://Record.txt");

	CFileException e;

	//创建目标文档文件;
	if( !recordFile.Open( fileName , CFile::modeWrite , &e ) )
	{
		AfxMessageBox( "建立目标文档文件失败!");
		return;
	}

	char ctrl = 0x0D;
	char line = 0x0A;
	recordFile.Write( "==============================" , 30 ); 
	recordFile.Write( &ctrl , 1 ); 
	recordFile.Write( &line , 1 );

	int k = 0;
	for( i = m_width*m_height - 1 ; i >= 0 ; i-- )
	{
		char ch[20];
		
		itoa( m_recordTable[ i ].x , ch , 10 );
		recordFile.Write( (CString)ch, 1 );
		
		itoa( m_recordTable[ i ].y , ch , 10 );
		recordFile.Write( (CString)ch, 1 );

		recordFile.Write( " " , 1 );

		if( (++k)%m_width == 0 )
		{
			recordFile.Write( &ctrl , 1 ); 
			recordFile.Write( &line , 1 );
		}
	}
		
	recordFile.Close();	
}
//###########################################################################
//功能  :
//          从指定的起始位置开始搜索
//参数  :
//          curLoc   :   当前搜索的起始位置
//返回值:
//          true     :   搜索成功
//          false    :   搜索失败
//###########################################################################
bool  CChessCalculator::Search( Location curLoc )//开始计算;
{
	m_complex++;
	
	//修改棋盘标志;
	m_chessTable[curLoc.x-1][curLoc.y-1] = 1;
	
	//是否搜索成功结束标志;
	if( isSuccess() )
		return true;
	
	//还有未走到的棋盘点,从当前位置开始搜索;
	else
	{
		//递归搜索未走过的棋盘点;
		for( int i = 0 ; i < 8 ; i++ )
		{
			Location newLocation = GetSubTreeNode( curLoc , i ) ;
			if( isValide( newLocation ) && m_chessTable[newLocation.x-1][newLocation.y-1] == 0 )
			{		
				if( Search( newLocation ) == true )
				{
					//填写记录表;
					MarkInTable( newLocation, curLoc );
					return true;
				}
			}	
		}
	}
	//搜索失败,恢复棋盘标志;
	m_chessTable[curLoc.x-1][curLoc.y-1] = 0;
	return false;
}
//###########################################################################
//功能  :
//          取得当前棋盘的宽度
//返回值:
//          棋盘宽度
//###########################################################################
int  CChessCalculator::GetWidth()//取得棋盘的宽度;
{
	return m_width;
}
//###########################################################################
//功能  :
//          取得当前棋盘的高度
//返回值:
//          棋盘高度
//###########################################################################
int  CChessCalculator::GetHeight()//取得棋盘的高度;
{ 
	return m_height;
}

//###########################################################################
//功能  :
//          在走子记录表中查找是否包含指定的位置
//参数  :
//          loc    :  指定要查找的位置
//          n      :  当前走子记录表的大小
//返回值:
//          true   :  指定位置已经在走子记录表中
//          false  :  指定位置不包含在走子记录表中
//###########################################################################
bool CChessCalculator::FindInTable( Location loc , int n )
{
	for( int i = 0 ; i < n ; i ++ )
	{
		if( loc.x == m_recordTable[i].x && loc.y == m_recordTable[i].y )
			return true;
	}
	return false;	
}
//###########################################################################
//功能:
//       填写指定的当前位置和新位置到走子记录表中
//参数:
//       newLoc   :   新位置
//       curLoc   :   当前位置
//###########################################################################
void CChessCalculator::MarkInTable( Location newLoc , Location curLoc )
{
	if( FindInTable( newLoc , m_index ) == false )
		m_recordTable[m_index++] = newLoc;	
	
	if( FindInTable( curLoc , m_index ) == false )
		m_recordTable[m_index++] = curLoc;
}
//###########################################################################
//功能  :
//          判断当前位置是否合法
//返回值:  
//          true  :  位置合法
//          false :  位置不合法
//###########################################################################
bool CChessCalculator::isValide( Location& loc )
{
	if( loc.x >= 1 && loc.x <= m_width && loc.y >= 1 && loc.y <= m_height )
		return true;
	else
		return false;
}
//###########################################################################
//功能  :
//        判断搜索是否成功
//返回值:
//        true  : 搜索成功
//        false : 搜索未完成
//###########################################################################
bool CChessCalculator::isSuccess()
{
	for( int i = 0 ; i < m_height ; i++ )
		for( int j = 0 ; j < m_width ; j++ )
			if( m_chessTable[i][j] == 0 )
				return false;
	return true;
}
//###########################################################################
//功能  :      
//            取得从当前位置出发可以到达的下一个新位置
//参数  :     
//            curLoc  |   当前位置       
//             i      |   方向(0-7)
//返回值:      
//            从当前位置的指定方向出发可以到达的新位置
//###########################################################################
Location CChessCalculator::GetSubTreeNode( Location curLoc , int i )
{
	Location newLoc;
	switch( i )
	{
	case 0:
		newLoc.x = curLoc.x + 1;
		newLoc.y = curLoc.y + 2;
		break;
	case 1:
		newLoc.x = curLoc.x + 1;
		newLoc.y = curLoc.y - 2;
		break;

	case 2:
		newLoc.x = curLoc.x - 1;
		newLoc.y = curLoc.y + 2;
		break;

	case 3:
		newLoc.x = curLoc.x - 1;
		newLoc.y = curLoc.y - 2;
		break;

	case 4:
		newLoc.x = curLoc.x + 2;
		newLoc.y = curLoc.y + 1;
		break;

	case 5:
		newLoc.x = curLoc.x + 2;
		newLoc.y = curLoc.y - 1;
		break;

	case 6:
		newLoc.x = curLoc.x - 2;
		newLoc.y = curLoc.y + 1;
		break;

	case 7:
		newLoc.x = curLoc.x - 2;
		newLoc.y = curLoc.y - 1;
		break;

	default:
		//errors, it will never go to here;
		break;
	}
	return newLoc;
	
}
//###########################################################################
//功能:
//       图形化显示搜索结果
//参数:
//       CDC*   |   绘图环境
//###########################################################################
void CChessCalculator::DisplayResult( CDC* pDC )
{
	CPen   newPen;
	CPen*  oldPen;
	
	newPen.CreatePen( PS_SOLID , 2 , RGB( 225 , 225 , 225 ) );
	oldPen = pDC->SelectObject( &newPen );
	
	int indexOnX = 60;
	int indexOnY = 60;
	
	CPoint startPoint;
	CPoint endPoint;
	CPoint ChessTableStartLocation(60,60);
	
	startPoint  = ChessTableStartLocation;
	
	endPoint    = ChessTableStartLocation;
	endPoint.x += ( m_width - 1 )*indexOnX ;

	pDC->SetBkMode( TRANSPARENT  );
	
	//绘制棋盘；
	for( int i = 0 ; i < m_height ; i++ )
	{
		endPoint.y = ChessTableStartLocation.y + i*indexOnY;
		startPoint.y = ChessTableStartLocation.y + i*indexOnY;
		
		pDC->MoveTo( startPoint );
		pDC->LineTo( endPoint );
		
		char str[10];
		itoa( i+1 , str , 10 );
		pDC->TextOut( startPoint.x - 40 , startPoint.y - 3 , (CString)str );
	}
	
	startPoint  = ChessTableStartLocation;
	endPoint    = ChessTableStartLocation;
	endPoint.y += (m_height-1)*indexOnY ;
	
	for( int j = 0 ; j < m_width ; j++ )
	{
		endPoint.x = ChessTableStartLocation.x + j*indexOnX;
		startPoint.x = ChessTableStartLocation.x + j*indexOnX;
		
		pDC->MoveTo( startPoint );
		pDC->LineTo( endPoint );	
		
		char str[10];
		itoa( j+1 , str , 10 );
		pDC->TextOut( startPoint.x -3 , startPoint.y - 40 , (CString)str );
	}

	CPoint chessPosition ;
	//绘制棋子走子过程；
	int k = 0;
	for( i = m_width*m_height - 1 ; i >= 0  ; i-- )
	{
		chessPosition.x = ChessTableStartLocation.y + (m_recordTable[i].y - 1)*indexOnX;
		chessPosition.y = ChessTableStartLocation.x + (m_recordTable[i].x - 1)*indexOnY;
		
		CRect rect;
		rect.top = chessPosition.y - 20;
		rect.bottom = chessPosition.y + 20;
		rect.left = chessPosition.x - 20;
		rect.right = chessPosition.x + 20;
		pDC->Ellipse( rect );
		
		char str[10];
		itoa( k+1 , str , 10 );
		rect.top += 10;
		pDC->DrawText( (CString)str , rect , 1 );
		
		k++;
		if( m_showDelay == true )
	    	Sleep(900);
	}

}
//###########################################################################
//功能  :
//     取得当前的搜索状态 
//     |   WAITING     |   WORKING  |  SUCCESS   |  FAILED
//     |  等待开始搜索 |   正在搜索 |  搜索成功  |  搜索失败
//
//返回值:
//     当前搜索状态
//###########################################################################
Status CChessCalculator::GetCalculateResult()
{
	if( !m_start )
		return WAITING;	

	else if( m_start && !m_end )
		return WORKING;

	else if( m_result == true )
		return SUCCESS;

	else if( m_end && !m_result )
		return FAILED;
}
//###########################################################################
//功能  :
//         取得当前已经搜索的解空间大小
//返回值: 
//         搜索解空间大小 
//###########################################################################
int CChessCalculator::GetSearchSpace()
{
	return m_complex;
}
//###########################################################################
//功能:
//       设置显示结果模式
//参数:
//       delay = true  :  动画显示 
//       delay = false :  直接显示 
//###########################################################################
void CChessCalculator::SetShowDelay(bool delay)
{
	m_showDelay = delay; 

}