問題描述：一個騎士在棋盤中，給予其一個初始位置，求其是否能夠走完整個棋盤。
騎士的走法和中國象棋的馬走法相同，在前進過程中，騎士在其落足過的地方不能再次落足。
代碼如下：
~~~
//騎士走棋盤問題，騎士的走法與象棋中馬的走法相同，要求騎士便利棋盤中所有的點，但不能重復走一個點兩次
//本題采用優先選擇+回溯到方法進行，每次最先選擇下一次能走路徑最少的點
#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");
}
~~~
