Shulou(Shulou.com)06/01 Report--

This article mainly describes how to use C/C++ to achieve horse pedal chessboard algorithm, the text is very detailed, has a certain reference value, interested friends must read!

specific contents are as follows

Problem description: Put the horse randomly in a square of Board[0~7][0 ~ 7] of 8×8 chess board, and the horse moves according to the rules of chess. Each square is required to be entered only once, and all 64 squares on the chessboard are traversed.

Problem solving algorithm brief description:

1. depth-first traversal + backtracking

2. Greedy algorithm + depth-first traversal + backtracking

Solution 1 Description:

1. Use a two-dimensional array Step[8][8]= {-1} to represent the chessboard, the starting position is the current position Step[i][j], set NumOfSteps = 0;

2. Step[i][j] =NumOfSteps++,

If NumOfSteps == 64 indicates that the solution has been obtained, exit;

If 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 tPos.nPosX || tPos.nPosX +1 >

CHESS_BOARD_LINE_NUM || 0 > tPos.nPosY || tPos.nPosY + 1 > CHESS_BOARD_COLUM_NUM);} //检查位置是否已经跳过，若跳过则位置上记录经过该位置时为第几跳，若未被跳过则值为棋盘初始值-1int 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;} //初始化棋盘上所有位置的值为-1void 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;}以上是"如何使用C/C++实现马踏棋盘算法"这篇文章的所有内容，感谢各位的阅读!希望分享的内容对大家有帮助，更多相关知识，欢迎关注行业资讯频道!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.