C++实现马踏棋盘算法：深度优先与贪心策略详解

#include<stdio.h>
 
//定义棋盘的行数和列数
#define CHESS_BOARD_LINE_NUM 10
#define CHESS_BOARD_COLUM_NUM 10
 
//定义棋盘上位置的结构体
typedef struct 
{
	int nPosX;
	int nPosY;
}SPOS;
 
//使用一个二维数组来表示棋盘
int g_ArrChessBoard[CHESS_BOARD_LINE_NUM][CHESS_BOARD_COLUM_NUM];
 
//用来表示Horse跳到下一位置为第几跳，起跳位置为第0跳
int g_HorseSteps = 0;
 
//定义Horse的起跳位置，可以输入；若输入非法则使用默认起跳位置(0,0)
SPOS g_StartPos={0,0};
 
//检查位置有效性, 若位置在棋盘内则返回1，不在棋盘则返回0
int checkPos(SPOS tPos)
{
	//X/Y坐标不在棋盘内则位置不在棋盘内
    return !(0 > tPos.nPosX || tPos.nPosX +1 > CHESS_BOARD_LINE_NUM || 0 > tPos.nPosY || tPos.nPosY + 1 > CHESS_BOARD_COLUM_NUM);
}
 
//检查位置是否已经跳过，若跳过则位置上记录经过该位置时为第几跳，若未被跳过则值为棋盘初始值-1
int checkUsed(SPOS tPos)
{
	return g_ArrChessBoard[tPos.nPosX][tPos.nPosY] != -1;
}
 
//根据偏移量获取位置有效性
void getNextStepListByOffSet(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep, int offSetX, int offSetY)
{
	//定义Horse的可跳方向
	//分别为右上（1,1）、右下（1，-1）、左上（-1，1）、左下（-1，-1）
	//原始坐标+方向位移得到新的跳点
	static SPOS DirectionList[4] = {{1,1},{1,-1},{-1,1},{-1,-1}};
    SPOS tPos; //存储可能的跳点，该跳点不一定有效
	int i = 0;
 
	for (; i < 4; i++)
	{
		tPos.nPosX = curPos.nPosX + offSetX*DirectionList[i].nPosX;
		tPos.nPosY = curPos.nPosY + offSetY*DirectionList[i].nPosY;
	
		//若跳点在棋盘内，且跳点未被跳过则可以作为下一跳点
		if (checkPos(tPos) && !checkUsed(tPos))
		{
			NextStepList[(*NumOfValidStep)++] = tPos;
		}
	}
}
 
//获取下一跳位置列表, 下一跳位置列表最多存在8个，所以固定传入数组8
//只返回有效的位置列表， NumOfValidStep中存储有效位置列表个数
void getNextStepList(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep)
{
	//X坐标移动2格，Y坐标移动1格检查
    getNextStepListByOffSet(curPos, NextStepList, NumOfValidStep, 2, 1);   
	  
	//X坐标移动1格，Y坐标移动2格检查
	getNextStepListByOffSet(curPos, NextStepList, NumOfValidStep, 1, 2);   
}
 
//冒泡排序
void sortByNextStepNum(SPOS NextStepList[8], int* NumOfValidStep, int nSubValidStep[8])
{
	int tmpN;
	SPOS tmpPos;
	int i = 0;
	int j = 0;
	int MaxStepNum = *NumOfValidStep;
	for (; i < MaxStepNum; i++)
	{
		for (j = 1; j < MaxStepNum - i; j++)
		{
			if (nSubValidStep[j] < nSubValidStep[j-1])
			{
				//进行位置互换，进行冒泡
				tmpN = nSubValidStep[j];
				nSubValidStep[j] = nSubValidStep[j-1];
				nSubValidStep[j-1] = tmpN;
				
				//进行对应的Pos互换
				tmpPos = NextStepList[j];
				NextStepList[j] = NextStepList[j-1];
				NextStepList[j-1] = tmpPos;
			}
		}
	}
}
 
//使用贪心算法获取下一位置列表，即对返回的有效列表根据出口进行升序排列
void getNextGreedList(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep)
{
	SPOS subNextStepList[8]; //用于缓存下一跳点列表的中每个跳点的下一跳点列表
	int  nSubValidStep[8] = {0,0,0,0,0,0,0,0};  //用于存储下一跳点列表中每个跳点的下一跳点个数	
	int  i = 0;	

	//先获取所有的可跳节点
	getNextStepList(curPos, NextStepList, NumOfValidStep);
	
	//获取子跳点的下一跳点个数
	for(; i< *NumOfValidStep; i++)
	{
		getNextStepList(NextStepList[i], subNextStepList, &nSubValidStep[i]);
	}
	
	//使用冒泡排序
	sortByNextStepNum(NextStepList, NumOfValidStep, nSubValidStep);
}
 
 
//以输入Pos为起点进行马踏棋盘
//返回0  表示找到正确跳跃路径
//返回-1 表示已经完成所有跳点的尝试，不存在可行方案
//返回1  表示选中的下一跳并非可行路径，需要重新选择一个跳点进行尝试
int HorseRoaming(SPOS curPos)
{
	SPOS NextStepList[8];   //记录curPos的下一跳点列表，最多存在8个可能跳点，使用数组表示
	int  NumOfValidStep = 0;//记录下一跳列表中的跳点个数
	int  i = 0;
	int  nRet = 1;
	
	//添加跳点的Trace记录，并刷新跳点的计数
	g_ArrChessBoard[curPos.nPosX][curPos.nPosY] = g_HorseSteps++;
	
	//若已经经过棋盘上所有节点则表示找到马踏棋盘路径，退出
	if (g_HorseSteps == CHESS_BOARD_LINE_NUM*CHESS_BOARD_COLUM_NUM)
	{
		return 0;
	}
	
	
	//使用普通DFS进行路径查找
	//getNextStepList(curPos, NextStepList, &NumOfValidStep);
	
	//使用贪心算法获取有效列表
	getNextGreedList(curPos, NextStepList, &NumOfValidStep);
	
	for (; i < NumOfValidStep; i++)
	{
		//进行递归求解
		nRet = HorseRoaming(NextStepList[i]);
        if (1 != nRet)
        {
			//求解结束
			return nRet;
        }    
	}
	
	//若回到起点位置，且起点的所有可能跳点均已尝试过，则说明未找到遍历棋盘方案
	if (curPos.nPosX == g_StartPos.nPosY && curPos.nPosY == g_StartPos.nPosY)
	{
		return -1;
	}
	
	//回溯：回退棋盘上的Trace记录，并返回上层
	g_ArrChessBoard[curPos.nPosX][curPos.nPosY] = -1;
	g_HorseSteps--;
	return 1;
}
 
//初始化棋盘上所有位置的值为-1
void initBoard()
{
	int i,j; //设置循环控制变量
	for (i = 0; i< CHESS_BOARD_LINE_NUM; i++)
	{   
		for (j = 0; j< CHESS_BOARD_COLUM_NUM; j++)
		{
			g_ArrChessBoard[i][j] = -1;
		}
	}
}
 
//将棋盘上记录的跳跃Trace打印到文件中
void  printSteps()
{
	int i,j;   
	FILE* pfile = fopen("OutPut.txt","wb+");
	
	for (i = 0; i< CHESS_BOARD_LINE_NUM; i++)
	{
		for (j = 0; j< CHESS_BOARD_COLUM_NUM; j++)
		{
			fprintf(pfile,"%2d ", g_ArrChessBoard[i][j]);
		}
		fprintf(pfile,"\r\n");
	}
	
	fclose(pfile);
}
 
int main()
{
	//进行棋盘上跳跃Trace初始化
	initBoard();
	if (HorseRoaming(g_StartPos) == 0)
	{
		//打印结果
		printSteps();
	}
	else
	{
		//未找到解
		printf("Not found Result \n");
	}
	return 0;
}