horsetravel.cpp

一个解决国际象棋的马周游问题的算法.本程序使用改善后的回溯算法来加速问题的解决.

// HorseTravel.cpp: implementation of the HorseTravel class.
//
//////////////////////////////////////////////////////////////////////
#include "HorseTravel.h"

/********************************************************************
*	Author: fire
*	Time: 2007.10.15
*********************************************************************/
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

int HorseTravel::s_drow[8] = {2,2,1,-1,-2,-2,-1,1};
int HorseTravel::s_dcol[8] = {-1,1,2,2,1,-1,-2,-2}; 
bool HorseTravel::s_bStop = false;

HorseTravel::HorseTravel(int StartRow, int StartCol, int ChessSize)
{
	int i,j;

	//m_ways[8] = {0,1,2,3,4,5,6,7};
	m_iStartRow = StartRow;
	m_iStartCol = StartCol;
	m_n = ChessSize;
	
	m_Path = new Node[m_n*m_n];
	m_Access = new bool*[m_n];
	for(i=0; i<m_n; i++)
	{
		m_Access[i] = new bool[m_n];
	}
	for(i=0; i<m_n; i++)
	{
		for(j=0; j<m_n; j++)
		{
			m_Access[i][j] = false;
			m_Path[i*m_n+j].index = -1;
		}
	}
	m_bFlag = false;

	SetStart();
}

HorseTravel::~HorseTravel()
{
	int i;
	delete []m_Path;
	for(i=0; i<m_n; i++)
	{
		delete []m_Access[i];
	}
	delete []m_Access;
}

bool HorseTravel::Check(int row, int col)
{
	if( row<0 || row>m_n-1)
	{
		return false;
	}
	if( col<0 || col>m_n-1)
	{
		return false;
	}
	if( m_Access[row][col] == true )
	{
		return false;
	}
	return true;
}

void HorseTravel::CountDirtWays(int row, int col)
{
	int i,j;
	int counter;
	int dirt_row,dirt_col;

	for(i=0; i<8; i++)
	{
		dirt_row = row + s_drow[i];
		dirt_col = col + s_dcol[i];
		if(!Check(dirt_row,dirt_col))
		{
			//不合法的方向,将其出口数设为9,使其排在最后
			m_ways[i] = 9;
			continue;
		}
		counter = 0;
		for(j=0; j<8; j++)
		{
			if(Check(dirt_row + s_drow[j], dirt_col + s_dcol[j]))
			{
				counter++;
			}
		}
		m_ways[i] = counter;
	}
}

void HorseTravel::DirtWaySort(int k)
{
	int i,j;
	int row = m_Path[k].row;
	int col = m_Path[k].col;
	int* dirt = m_Path[k].dirt;

	CountDirtWays(row, col);
	for(i=0; i<8; i++)
	{
		dirt[i] = i;
	}
	// 将8个方向按照出口数的大小作非降序排序(插入排序),
	// 以便使出口数较少的方向先被搜索
	for(i=1; i<8; i++)
	{
		int temp = dirt[i];
		for(j=i-1; j>=0; j--)
		{
			if(m_ways[dirt[j]]>m_ways[temp])
			{
				dirt[j+1] = dirt[j];
			}
			else break;
		}
		dirt[j+1] = temp;
	}
}

void HorseTravel::HouseTravelIter()
{
	int trow,tcol;
	int n = m_n*m_n;
	int k = 1;

	m_Path[0].row = m_iStartRow;
	m_Path[0].col = m_iStartCol;
	m_Access[m_iStartRow][m_iStartCol] = true;
	/////////////////////////////////////////////////////////////////优化部分
	DirtWaySort(0);
	/////////////////////////////////////////////////////////////////

	while( k>=1 )
	{
		while(m_Path[k-1].index<=6)
		{
			if (s_bStop) return;
			m_Path[k-1].index++;
			int i = m_Path[k-1].index;
			/////////////////////////////////////////////////////////优化部分
			trow = m_Path[k-1].row+s_drow[m_Path[k-1].dirt[i]];
			tcol = m_Path[k-1].col+s_dcol[m_Path[k-1].dirt[i]];
			/////////////////////////////////////////////////////////
			if( (k == n) && (trow == m_iStartRow) && (tcol == m_iStartCol) )
			{
				m_bFlag = true;
				return;
			}
			else if( (k < n) && Check(trow,tcol))
			{
				m_Path[k].row = trow;
				m_Path[k].col = tcol;
				m_Access[trow][tcol] = true;
				////////////////////////////////////////////////////优化部分
				DirtWaySort(k);
				////////////////////////////////////////////////////
				k++;
			}
		}
		m_Access[m_Path[k-1].row][m_Path[k-1].col] = false;
		m_Path[k-1].index = -1;
		k--;
	}
}