骑士旅行问题骑士棋盘

骑士旅游

问题描述：一个骑士在棋盘中,给予其一个初始位置,求其是否能够走完整个棋盘。

骑士的走法和中国象棋的马走法相同,骑士在其落足过的地方不能再次落足,在前进过程中。

#include 。

using namespace std;。

#define MAX_SIZE 9。

int nAlreayVisit = 0;。

int nChessBoard[MAX_SIZE][MAX_SIZE]; //模拟棋盘状况,0表示没有被访问过。

int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; //可访问的各个点相对当前点位置。

int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1};。

//int nArray。

void PrintChessBoard()。

{

cout<

for (int i = 0; i< MAX_SIZE; i++)。

{

for (int j = 0; j < MAX_SIZE; j++)。

{

cout<

}

cout<

}

}

//测试该位置有多少个下一步的路径可选。

int TestNextWay(int nTestX, int nTestY)。

{

int tempX,tempY;。

int nRet = 0;。

for (int i = 0; i< 8; i++)。

{

tempX = nTestX + ktmove1[i];。

tempY = nTestY + ktmove2[i];。

if (tempX > -1 && tempX < MAX_SIZE && tempY > -1 && tempY < MAX_SIZE && nChessBoard[tempX][tempY] == 0)。

{

nRet++;

}

}

return nRet;。

}

bool KnightTour(int nStartX, int nStartY)。

{

nAlreayVisit++; //当前点被访问了。

nChessBoard[nStartX][nStartY] = nAlreayVisit; //表示其被访问的次序。

//PrintChessBoard();。

if(nAlreayVisit == MAX_SIZE*MAX_SIZE) //棋盘上的所有点都已经被访问过了,返回true。

{

return true;。

}

//选取下一个要访问的点。

int nCanVisit[MAX_SIZE][2];。

int nCanNum = 0; //下一步可以走到选择方法。

int tempX,tempY;。

int nNextWay = 0;。

int NextX, NextY; //下一步要走的坐标。

int nLeastWay = 9;。

//选取下下步走法最少的路径。

for (int i = 0; i< 8; i++)。

{

tempX = nStartX + ktmove1[i];。

tempY = nStartY + ktmove2[i];。

if (tempX > -1 && tempX < MAX_SIZE && tempY > -1 && tempY < MAX_SIZE && nChessBoard[tempX][tempY] == 0)。

{

nCanVisit[nCanNum][0] = tempX;。

nCanVisit[nCanNum][1] = tempY;。

nCanNum++;。

nNextWay = TestNextWay(tempX,tempY);。

if (nNextWay < nLeastWay)。

{

nLeastWay = nNextWay;。

NextX = tempX;。

NextY = tempY;。

}

}

}

bool bFlag = false;。

if (nCanNum == 0) //无法继续走下去了。

{

nAlreayVisit--; //当前点访问被撤销。

nChessBoard[nStartX][nStartY] = 0;。

return false;。

}

else

{

bFlag = KnightTour(NextX,NextY);。

if (bFlag)。

{

return true;。

}

else

{

for (int k = 0; k< nCanNum; k++)。

{

bFlag = KnightTour(nCanVisit[k][0], nCanVisit[k][1]);。

if (bFlag)。

{

return true;。

}

}

}

}

//遍历完所有可走节点都无法完成。

nAlreayVisit--; //当前点访问被撤销。

nChessBoard[nStartX][nStartY] = 0;。

return false;。

}

int main()。

{

int x,y;

cout<<'请输入起始位置坐标x和y(即数组的下标,为0到7范围)'<

cin>>x>>y;。

memset(nChessBoard, 0, sizeof(nChessBoard));。

if (KnightTour(x,y))。

{

cout<<'遍历棋盘成功'<

PrintChessBoard();。

}

else

cout<<'遍历1棋盘失败'<

system('pause');。

}