如何使用C/C++实现马踏棋盘算法
如何使用C/C++实现马踏棋盘算法
这篇文章主要介绍如何使用C/C++实现马踏棋盘算法，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
具体内容如下
问题描述：将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。
问题求解算法简述：
1.深度优先遍历+回溯法
2.贪心算法+深度优先遍历+回溯法
解法1描述：
1.使用一个二维数组Step[8][8]= {-1}来表示棋盘，起跳位置做为当前位置Step[i][j]，设置NumOfSteps = 0；
2.设置当前位置Step[i][j] =NumOfSteps++,
若NumOfSteps == 64表示已经获取解，退出；
若NumOfSteps < 64，获取位置Step[i][j]的下一跳可达位置列表NextStepList，设置N=0；【可达位置列表必须保证该位置有效，且未被经过】
3.从NextStepList获取下一个未处理位置NextStepList[N]，将NextStepList[N]作为当前位置Step[i][j],执行第2步
若列表已经结束，则设置当前Step[i][j] = -1
若Step[i][j]==起跳位置，表示无解，退出
否则设置NumOfSteps--，回溯到上一跳位置，在上一跳位置继续执行第3步；
解法2描述：
1.使用一个二维数组Step[8][8]= {-1}来表示棋盘，起跳位置做为当前位置Step[i][j]，设置NumOfSteps = 0；
2.设置当前位置Step[i][j] =NumOfSteps++,
若NumOfSteps==64表示已经获取解，退出；
若NumOfSteps<64，获取位置Step[i][j]的下一跳可达位置列表NextStepList，设置N=0；【可达位置列表必须保证该位置有效，且未被经过】
3.从NextStepList获取下一个未处理位置NextStepList[N]，将NextStepList[N]作为当前位置Step[i][j],执行第2步
若列表已经结束，则设置当前Step[i][j] = -1
若Step[i][j]==起跳位置，表示无解，退出
否则设置NumOfSteps--，回溯到上一跳位置，在上一跳位置继续执行第3步；
具体实现如下：
#include<stdio.h>//定义棋盘的行数和列数#defineCHESS_BOARD_LINE_NUM10#defineCHESS_BOARD_COLUM_NUM10//定义棋盘上位置的结构体typedefstruct{intnPosX;intnPosY;}SPOS;//使用一个二维数组来表示棋盘intg_ArrChessBoard[CHESS_BOARD_LINE_NUM][CHESS_BOARD_COLUM_NUM];//用来表示Horse跳到下一位置为第几跳，起跳位置为第0跳intg_HorseSteps=0;//定义Horse的起跳位置，可以输入；若输入非法则使用默认起跳位置(0,0)SPOSg_StartPos={0,0};//检查位置有效性,若位置在棋盘内则返回1，不在棋盘则返回0intcheckPos(SPOStPos){//X/Y坐标不在棋盘内则位置不在棋盘内return!(0>tPos.nPosX||tPos.nPosX+1>CHESS_BOARD_LINE_NUM||0>tPos.nPosY||tPos.nPosY+1>CHESS_BOARD_COLUM_NUM);}//检查位置是否已经跳过，若跳过则位置上记录经过该位置时为第几跳，若未被跳过则值为棋盘初始值-1intcheckUsed(SPOStPos){returng_ArrChessBoard[tPos.nPosX][tPos.nPosY]!=-1;}//根据偏移量获取位置有效性voidgetNextStepListByOffSet(SPOScurPos,SPOSNextStepList[8],int*NumOfValidStep,intoffSetX,intoffSetY){//定义Horse的可跳方向//分别为右上（1,1）、右下（1，-1）、左上（-1，1）、左下（-1，-1）//原始坐标+方向位移得到新的跳点staticSPOSDirectionList[4]={{1,1},{1,-1},{-1,1},{-1,-1}};SPOStPos;//存储可能的跳点，该跳点不一定有效inti=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中存储有效位置列表个数voidgetNextStepList(SPOScurPos,SPOSNextStepList[8],int*NumOfValidStep){//X坐标移动2格，Y坐标移动1格检查getNextStepListByOffSet(curPos,NextStepList,NumOfValidStep,2,1);//X坐标移动1格，Y坐标移动2格检查getNextStepListByOffSet(curPos,NextStepList,NumOfValidStep,1,2);}//冒泡排序voidsortByNextStepNum(SPOSNextStepList[8],int*NumOfValidStep,intnSubValidStep[8]){inttmpN;SPOStmpPos;inti=0;intj=0;intMaxStepNum=*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;}}}}//使用贪心算法获取下一位置列表，即对返回的有效列表根据出口进行升序排列voidgetNextGreedList(SPOScurPos,SPOSNextStepList[8],int*NumOfValidStep){SPOSsubNextStepList[8];//用于缓存下一跳点列表的中每个跳点的下一跳点列表intnSubValidStep[8]={0,0,0,0,0,0,0,0};//用于存储下一跳点列表中每个跳点的下一跳点个数inti=0;//先获取所有的可跳节点getNextStepList(curPos,NextStepList,NumOfValidStep);//获取子跳点的下一跳点个数for(;i<*NumOfValidStep;i++){getNextStepList(NextStepList[i],subNextStepList,&nSubValidStep[i]);}//使用冒泡排序sortByNextStepNum(NextStepList,NumOfValidStep,nSubValidStep);}//以输入Pos为起点进行马踏棋盘//返回0表示找到正确跳跃路径//返回-1表示已经完成所有跳点的尝试，不存在可行方案//返回1表示选中的下一跳并非可行路径，需要重新选择一个跳点进行尝试intHorseRoaming(SPOScurPos){SPOSNextStepList[8];//记录curPos的下一跳点列表，最多存在8个可能跳点，使用数组表示intNumOfValidStep=0;//记录下一跳列表中的跳点个数inti=0;intnRet=1;//添加跳点的Trace记录，并刷新跳点的计数g_ArrChessBoard[curPos.nPosX][curPos.nPosY]=g_HorseSteps++;//若已经经过棋盘上所有节点则表示找到马踏棋盘路径，退出if(g_HorseSteps==CHESS_BOARD_LINE_NUM*CHESS_BOARD_COLUM_NUM){return0;}//使用普通DFS进行路径查找//getNextStepList(curPos,NextStepList,&NumOfValidStep);//使用贪心算法获取有效列表getNextGreedList(curPos,NextStepList,&NumOfValidStep);for(;i<NumOfValidStep;i++){//进行递归求解nRet=HorseRoaming(NextStepList[i]);if(1!=nRet){//求解结束returnnRet;}}//若回到起点位置，且起点的所有可能跳点均已尝试过，则说明未找到遍历棋盘方案if(curPos.nPosX==g_StartPos.nPosY&&curPos.nPosY==g_StartPos.nPosY){return-1;}//回溯：回退棋盘上的Trace记录，并返回上层g_ArrChessBoard[curPos.nPosX][curPos.nPosY]=-1;g_HorseSteps--;return1;}//初始化棋盘上所有位置的值为-1voidinitBoard(){inti,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打印到文件中voidprintSteps(){inti,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);}intmain(){//进行棋盘上跳跃Trace初始化initBoard();if(HorseRoaming(g_StartPos)==0){//打印结果printSteps();}else{//未找到解printf("NotfoundResult\n");}return0;}
以上是“如何使用C/C++实现马踏棋盘算法”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注恰卡编程网行业资讯频道！
