如何使用C/C++實(shí)現(xiàn)馬踏棋盤算法

這篇文章主要介紹如何使用C/C++實(shí)現(xiàn)馬踏棋盤算法，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

具體內(nèi)容如下

問題描述：將馬隨機(jī)放在國際象棋的8×8棋盤Board[0～7][0～7]的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。

問題求解算法簡述：

1.深度優(yōu)先遍歷+回溯法

2.貪心算法+深度優(yōu)先遍歷+回溯法

解法1描述：

1.使用一個(gè)二維數(shù)組Step[8][8]= {-1}來表示棋盤，起跳位置做為當(dāng)前位置Step[i][j]，設(shè)置NumOfSteps = 0；

2.設(shè)置當(dāng)前位置Step[i][j] =NumOfSteps++,

若NumOfSteps == 64表示已經(jīng)獲取解，退出；

若NumOfSteps < 64，獲取位置Step[i][j]的下一跳可達(dá)位置列表NextStepList，設(shè)置N=0；【可達(dá)位置列表必須保證該位置有效，且未被經(jīng)過】

3.從NextStepList獲取下一個(gè)未處理位置NextStepList[N]，將NextStepList[N]作為當(dāng)前位置Step[i][j],執(zhí)行第2步

若列表已經(jīng)結(jié)束，則設(shè)置當(dāng)前Step[i][j] = -1

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

否則設(shè)置NumOfSteps--，回溯到上一跳位置，在上一跳位置繼續(xù)執(zhí)行第3步；

解法2描述：

1.使用一個(gè)二維數(shù)組Step[8][8]= {-1}來表示棋盤，起跳位置做為當(dāng)前位置Step[i][j]，設(shè)置NumOfSteps = 0；

2.設(shè)置當(dāng)前位置Step[i][j] =NumOfSteps++,

若NumOfSteps==64表示已經(jīng)獲取解，退出；

若NumOfSteps<64，獲取位置Step[i][j]的下一跳可達(dá)位置列表NextStepList，設(shè)置N=0；【可達(dá)位置列表必須保證該位置有效，且未被經(jīng)過】

3.從NextStepList獲取下一個(gè)未處理位置NextStepList[N]，將NextStepList[N]作為當(dāng)前位置Step[i][j],執(zhí)行第2步

若列表已經(jīng)結(jié)束，則設(shè)置當(dāng)前Step[i][j] = -1

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

否則設(shè)置NumOfSteps--，回溯到上一跳位置，在上一跳位置繼續(xù)執(zhí)行第3步；

具體實(shí)現(xiàn)如下：

#include<stdio.h>
 
 
//定義棋盤的行數(shù)和列數(shù)
#define CHESS_BOARD_LINE_NUM 10
#define CHESS_BOARD_COLUM_NUM 10
 
//定義棋盤上位置的結(jié)構(gòu)體
typedef struct 
{
    int nPosX;
    int nPosY;
}SPOS;
 
//使用一個(gè)二維數(shù)組來表示棋盤
int g_ArrChessBoard[CHESS_BOARD_LINE_NUM][CHESS_BOARD_COLUM_NUM];
 
//用來表示Horse跳到下一位置為第幾跳，起跳位置為第0跳
int g_HorseSteps = 0;
 
//定義Horse的起跳位置，可以輸入；若輸入非法則使用默認(rèn)起跳位置(0,0)
SPOS g_StartPos={0,0};
 
//檢查位置有效性, 若位置在棋盤內(nèi)則返回1，不在棋盤則返回0
int checkPos(SPOS tPos)
{
    //X/Y坐標(biāo)不在棋盤內(nèi)則位置不在棋盤內(nèi)
    return !(0 > tPos.nPosX || tPos.nPosX +1 > CHESS_BOARD_LINE_NUM || 0 > tPos.nPosY || tPos.nPosY + 1 > CHESS_BOARD_COLUM_NUM);
}
 
//檢查位置是否已經(jīng)跳過，若跳過則位置上記錄經(jīng)過該位置時(shí)為第幾跳，若未被跳過則值為棋盤初始值-1
int checkUsed(SPOS tPos)
{
    return g_ArrChessBoard[tPos.nPosX][tPos.nPosY] != -1;
}
 
//根據(jù)偏移量獲取位置有效性
void getNextStepListByOffSet(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep, int offSetX, int offSetY)
{
    //定義Horse的可跳方向
    //分別為右上（1,1）、右下（1，-1）、左上（-1，1）、左下（-1，-1）
    //原始坐標(biāo)+方向位移得到新的跳點(diǎn)
    static SPOS DirectionList[4] = {{1,1},{1,-1},{-1,1},{-1,-1}};
    SPOS tPos; //存儲(chǔ)可能的跳點(diǎn)，該跳點(diǎn)不一定有效
    int i = 0;
 
    for (; i < 4; i++)
    {
        tPos.nPosX = curPos.nPosX + offSetX*DirectionList[i].nPosX;
        tPos.nPosY = curPos.nPosY + offSetY*DirectionList[i].nPosY;
 
        //若跳點(diǎn)在棋盤內(nèi)，且跳點(diǎn)未被跳過則可以作為下一跳點(diǎn)
        if (checkPos(tPos) && !checkUsed(tPos))
        {
            NextStepList[(*NumOfValidStep)++] = tPos;
        }
    }
}
 
//獲取下一跳位置列表, 下一跳位置列表最多存在8個(gè)，所以固定傳入數(shù)組8
//只返回有效的位置列表， NumOfValidStep中存儲(chǔ)有效位置列表個(gè)數(shù)
void getNextStepList(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep)
{
    //X坐標(biāo)移動(dòng)2格，Y坐標(biāo)移動(dòng)1格檢查
    getNextStepListByOffSet(curPos, NextStepList, NumOfValidStep, 2, 1);    
    
    //X坐標(biāo)移動(dòng)1格，Y坐標(biāo)移動(dòng)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])
            {
                //進(jìn)行位置互換，進(jìn)行冒泡
                tmpN = nSubValidStep[j];
                nSubValidStep[j] = nSubValidStep[j-1];
                nSubValidStep[j-1] = tmpN;
                
                //進(jìn)行對(duì)應(yīng)的Pos互換
                tmpPos = NextStepList[j];
                NextStepList[j] = NextStepList[j-1];
                NextStepList[j-1] = tmpPos;
            }
        }
    }
}
 
//使用貪心算法獲取下一位置列表，即對(duì)返回的有效列表根據(jù)出口進(jìn)行升序排列
void getNextGreedList(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep)
{
    SPOS subNextStepList[8]; //用于緩存下一跳點(diǎn)列表的中每個(gè)跳點(diǎn)的下一跳點(diǎn)列表
    int  nSubValidStep[8] = {0,0,0,0,0,0,0,0};  //用于存儲(chǔ)下一跳點(diǎn)列表中每個(gè)跳點(diǎn)的下一跳點(diǎn)個(gè)數(shù)    
    int  i = 0; 
 
    //先獲取所有的可跳節(jié)點(diǎn)
    getNextStepList(curPos, NextStepList, NumOfValidStep);
    
    //獲取子跳點(diǎn)的下一跳點(diǎn)個(gè)數(shù)
    for(; i< *NumOfValidStep; i++)
    {
        getNextStepList(NextStepList[i], subNextStepList, &nSubValidStep[i]);
    }
    
    //使用冒泡排序
    sortByNextStepNum(NextStepList, NumOfValidStep, nSubValidStep);
}
 
 
//以輸入Pos為起點(diǎn)進(jìn)行馬踏棋盤
//返回0  表示找到正確跳躍路徑
//返回-1 表示已經(jīng)完成所有跳點(diǎn)的嘗試，不存在可行方案
//返回1  表示選中的下一跳并非可行路徑，需要重新選擇一個(gè)跳點(diǎn)進(jìn)行嘗試
int HorseRoaming(SPOS curPos)
{
    SPOS NextStepList[8];   //記錄curPos的下一跳點(diǎn)列表，最多存在8個(gè)可能跳點(diǎn)，使用數(shù)組表示
    int  NumOfValidStep = 0;//記錄下一跳列表中的跳點(diǎn)個(gè)數(shù)
    int  i = 0;
    int  nRet = 1;
    
    //添加跳點(diǎn)的Trace記錄，并刷新跳點(diǎn)的計(jì)數(shù)
    g_ArrChessBoard[curPos.nPosX][curPos.nPosY] = g_HorseSteps++;
    
    //若已經(jīng)經(jīng)過棋盤上所有節(jié)點(diǎn)則表示找到馬踏棋盤路徑，退出
    if (g_HorseSteps == CHESS_BOARD_LINE_NUM*CHESS_BOARD_COLUM_NUM)
    {
        return 0;
    }
    
    
    //使用普通DFS進(jìn)行路徑查找
    //getNextStepList(curPos, NextStepList, &NumOfValidStep);
    
    //使用貪心算法獲取有效列表
    getNextGreedList(curPos, NextStepList, &NumOfValidStep);
    
    for (; i < NumOfValidStep; i++)
    {
        //進(jìn)行遞歸求解
        nRet = HorseRoaming(NextStepList[i]);
        if (1 != nRet)
        {
            //求解結(jié)束
            return nRet;
        }        
    }
    
    //若回到起點(diǎn)位置，且起點(diǎn)的所有可能跳點(diǎn)均已嘗試過，則說明未找到遍歷棋盤方案
    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; //設(shè)置循環(huán)控制變量
    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()
{
    //進(jìn)行棋盤上跳躍Trace初始化
    initBoard();
    if (HorseRoaming(g_StartPos) == 0)
    {
        //打印結(jié)果
        printSteps();
    }
    else
    {
        //未找到解
        printf("Not found Result \n");
    }
    return 0;
}

以上是“如何使用C/C++實(shí)現(xiàn)馬踏棋盤算法”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！