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

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

代码如下：

//骑士走棋盘问题，骑士的走法与象棋中马的走法相同，要求骑士便利棋盘中所有的点，但不能重复走一个点两次
//本题采用优先选择+回溯到方法进行，每次最先选择下一次能走路径最少的点

#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");

}