骑士旅行问题（骑士走棋盘）
最后更新于：2022-04-01 10:11:43
问题描述：一个骑士在棋盘中，给予其一个初始位置，求其是否能够走完整个棋盘。
骑士的走法和中国象棋的马走法相同，在前进过程中，骑士在其落足过的地方不能再次落足。
代码如下：
~~~
//骑士走棋盘问题，骑士的走法与象棋中马的走法相同，要求骑士便利棋盘中所有的点，但不能重复走一个点两次
//本题采用优先选择+回溯到方法进行，每次最先选择下一次能走路径最少的点
#include <iostream>
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<<endl<<"已经访问的位置数目为："<<nAlreayVisit<<endl;
for (int i = 0; i< MAX_SIZE; i++)
{
for (int j = 0; j < MAX_SIZE; j++)
{
cout<<nChessBoard[i][j]<<" ";
}
cout<<endl;
}
}
//测试该位置有多少个下一步的路径可选
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范围)"<<endl;
cin>>x>>y;
memset(nChessBoard, 0, sizeof(nChessBoard));
if (KnightTour(x,y))
{
cout<<"遍历棋盘成功"<<endl;
PrintChessBoard();
}
else
cout<<"遍历1棋盘失败"<<endl;
system("pause");
}
~~~
