图的遍历-马踏棋盘算法/骑士周游

奥普瓯江

原理：




备注：占时想不出更好的方法改编这个算法，先理解



代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX 6

int chess[MAX][MAX];


int get_chess(int x, int y, int tag);
int judge_chess(int *x, int *y, int count);
void pri_chess();

void pri_chess()                        //打印棋盘，因为是全局变量所以直接打印即可
{
    for(int i = 0; i < MAX; i++)
    {
        for(int j = 0; j < MAX; j++)
        {
            printf("%4d", chess[i][j]);
        }
        putchar('\n');
    }
}
int judge_chess(int *x, int *y, int count)          //对八个方向进行判断，如判断成立赋予指针x或y新值
{
    switch(count)
    {
        case 0:{
            if(*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)        //左上
            {
                *x = *x - 2;                        //上面的if判断赋予指针新值
                *y = *y - 1;
                return 1;
            }
            break;
        }
        case 1:{
            if(*x - 2 >= 0 && *y + 1 < MAX && chess[*x - 2][*y + 1] == 0)        //左下
            {
                *x = *x - 2;
                *y = *y + 1;
                return 1;
            }
            break;
        }
        case 2:{
            if(*x - 1 >= 0 && *y + 2 < MAX && chess[*x - 1][*y + 2] == 0)        //下左
            {
                *x = *x - 1;
                *y = *y + 2;
                return 1;
            }
            break;
        }
        case 3:{
            if(*x + 1 < MAX && *y + 2 < MAX && chess[*x + 1][*y + 2] == 0)        //下右
            {
                *x = *x + 1;
                *y = *y + 2;
                return 1;
            }
            break;
        }
        case 4:{
            if(*x + 2 < MAX && *y + 1 < MAX && chess[*x + 2][*y + 1] == 0)        //右下
            {
                *x = *x + 2;
                *y = *y + 1;
                return 1;
            }
            break;
        }
        case 5:{
            if(*x + 2 < MAX && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0)        //右上
            {
                *x = *x + 2;
                *y = *y - 1;
                return 1;
            }
            break;
        }
        case 6:{
            if(*x + 1 < MAX && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)        //上右
            {
                *x = *x + 1;
                *y = *y - 2;
                return 1;
            }
            break;
        }
        case 7:{
            if(*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)        //上左
            {
                *x = *x - 1;
                *y = *y - 2;
                return 1;
            }
            break;
        }
        default:
            break;
       /*case 0:
                        if( *x+2 < MAX && *y-1>=0 && chess[*x+2][*y-1]==0 )        // 右上               //验证
                        {
                                *x = *x + 2;
                                *y = *y - 1;
                                return 1;
                        }
                        break;

                case 1:
                        if( *x+2 < MAX && *y+1 < MAX && chess[*x+2][*y+1]==0 )        //右下
                        {
                                *x = *x + 2;
                                *y = *y + 1;
                                return 1;
                        }
                        break;

                case 2:
                        if( *x+1 < MAX && *y-2 >= 0 && chess[*x+1][*y-2]==0 )                 //上右
                        {
                                *x = *x + 1;
                                *y = *y - 2;
                                return 1;
                        }
                        break;

                case 3:
                        if( *x+1 < MAX && *y+2 < MAX && chess[*x+1][*y+2]==0 )        //下右
                        {
                                *x = *x + 1;
                                *y = *y + 2;
                                return 1;
                        }
                        break;

                case 4:
                        if( *x-2 >= 0 && *y-1 >= 0 && chess[*x-2][*y-1]==0 )                //左上
                        {
                                *x = *x - 2;
                                *y = *y - 1;
                                return 1;
                        }
                        break;

                case 5:
                        if( *x-2 >= 0 && *y+1 < MAX && chess[*x-2][*y+1]==0 )                //左下
                        {
                                *x = *x - 2;
                                *y = *y + 1;
                                return 1;
                        }
                        break;

                case 6:
                        if( *x-1 >= 0 && *y-2 >= 0 && chess[*x-1][*y-2]==0 )                //上左
                        {
                                *x = *x - 1;
                                *y = *y - 2;
                                return 1;
                        }
                        break;

                case 7:
                        if( *x-1 >= 0 && *y+2 < MAX && chess[*x-1][*y+2]==0 )                //下左
                        {
                                *x = *x - 1;
                                *y = *y + 2;
                                return 1;
                        }
                        break;

                default:
                        break;*/

    }
    return 0;
}

int get_chess(int x, int y, int tag)
{
    int lx = x, ly = y, flag = 0, count = 0;

    chess[x][y] = tag;                               //初始传入函数中的1这个值先传如棋盘，这个永远不会变

    if(tag == MAX * MAX)
    {
        pri_chess();
        return 1;
    }
    flag = judge_chess(&lx, &ly, count);              //第一个judge_chess判断，开始传入的肯定是0因为count开始被赋予0这个值

    while(flag == 0 && count < MAX)                 //如果第一个judge_chess返回来的是0这个值那么及执行这个循环，这里有一个count++意思是在第一个judge_chess返回值同等的位置进行剩余方位的筛选
    {
        count++;                                    //剩余方位进行定位
        flag = judge_chess(&lx, &ly, count);        //筛选
    }

    while(flag)                                    //如果在第一个judge_chess判断返回的是1这个值及执行这个循环
    {
        if(get_chess(lx, ly, tag + 1))              //如果执行了while这个循环及这个if判断执行递归循环把tag+1这个值传入开始的chess棋盘中，如果get_chess递归逆释放中返回的是0
        {
            return 1;
        }

        lx = x;                                     //x、y值在逆释放的时候变化了，但是lx、ly未被从新赋值，所以这里需要x、y向其从新赋值
        ly = y;

        count++;                                    //count逆释放时被返回两个数，如循环失败再次对方向进行从新判断在这个时候count不归零而是用递归释放的数据
        flag = judge_chess(&lx, &ly, count);

        while(flag == 0 && count < MAX)
        {
            count++;
            flag = judge_chess(&lx, &ly, count);
        }
    }
    if(flag == 0)                                   //当递归执行逆释放之前会先执行该判断，因为棋盘走不下去了所以返回前先对该位置回复未输入数据的状态也就是从新赋值为0
    {
        chess[x][y] = 0;
    }

    return 0;

}

int main()
{
    for(int i = 0 ; i < MAX; i++)           //初始化棋盘
    {
        for(int j = 0; j < MAX; j++)
        {
            chess[i][j] = 0;
        }
    }

    if(!get_chess(2, 0, 1))                 //函数调用并赋予初始棋子坐标及值
    {
        printf("马踏棋盘失败了！");
    }

    return 0;
}

输出：