如何使用C/C++实现马踏棋盘算法

这篇文章主要介绍如何使用C/C++实现马踏棋盘算法，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

具体内容如下

问题描述：将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

问题求解算法简述：

深度优先遍历+回溯法

贪心算法+深度优先遍历+回溯法

解法1描述：

使用一个二维数组Step[8][8]= {-1}来表示棋盘，起跳位置做为当前位置Step[i][j]，设置NumOfSteps = 0；

设置当前位置Step[i][j] =NumOfSteps++,

若NumOfSteps == 64表示已经获取解，退出；

若NumOfSteps < 64，获取位置Step[i][j]的下一跳可达位置列表NextStepList，设置N=0；【可达位置列表必须保证该位置有效，且未被经过】

从NextStepList获取下一个未处理位置NextStepList[N]，将NextStepList[N]作为当前位置Step[i][j],执行第2步

若列表已经结束，则设置当前Step[i][j] = -1

若Step[i][j]==起跳位置，表示无解，退出

否则设置NumOfSteps--，回溯到上一跳位置，在上一跳位置继续执行第3步；

解法2描述：

使用一个二维数组Step[8][8]= {-1}来表示棋盘，起跳位置做为当前位置Step[i][j]，设置NumOfSteps = 0；

设置当前位置Step[i][j] =NumOfSteps++,

若NumOfSteps==64表示已经获取解，退出；

若NumOfSteps<64，获取位置Step[i][j]的下一跳可达位置列表NextStepList，设置N=0；【可达位置列表必须保证该位置有效，且未被经过】

从NextStepList获取下一个未处理位置NextStepList[N]，将NextStepList[N]作为当前位置Step[i][j],执行第2步

若列表已经结束，则设置当前Step[i][j] = -1

若Step[i][j]==起跳位置，表示无解，退出

否则设置NumOfSteps--，回溯到上一跳位置，在上一跳位置继续执行第3步；

具体实现如下：

#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，不在棋盘则返回0int 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);} //检查位置是否已经跳过，若跳过则位置上记录经过该位置时为第几跳，若未被跳过则值为棋盘初始值-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++实现马踏棋盘算法”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注编程网其他教程频道！