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>
 
 
//定义棋盘的行数和列数
#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;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。