马踏棋盘问题，小甲鱼答案有一部分没看明白

WwangHB

马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。
国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马走日”的规则将“马”进行移动，要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。

#include <stdio.h>

#define X 8
#define Y 8

int chess[X][Y];

// 找到下一个可走的位置
int next(int *px, int *py, int count)
{
        int x = *px;
        int y = *py;

        switch(count)
        {
        case 0:
                if (x+2<=X-1 && y-1>=0 && chess[x+2][y-1] == 0)
                {
                        *px = x + 2;
                        *py = y - 1;
                        return 1;
                }
                break;
        case 1:
                if (x+2<=X-1 && y+1<=Y-1 && chess[x+2][y+1] == 0)
                {
                        *px = x + 2;
                        *py = y + 1;
                        return 1;
                }
                break;
        case 2:
                if (x+1<=X-1 && y-2>=0 && chess[x+1][y-2] == 0)
                {
                        *px = x + 1;
                        *py = y - 2;
                        return 1;
                }
                break;
        case 3:
                if (x+1<=X-1 && y+2<=Y-1 && chess[x+1][y+2] == 0)
                {
                        *px = x + 1;
                        *py = y + 2;
                        return 1;
                }
                break;
        case 4:
                if (x-2>=0 && y-1>=0 && chess[x-2][y-1] == 0)
                {
                        *px = x - 2;
                        *py = y - 1;
                        return 1;
                }
                break;
        case 5:
                if (x-2>=0 && y+1<=Y-1 && chess[x-2][y+1] == 0)
                {
                        *px = x - 2;
                        *py = y + 1;
                        return 1;
                }
                break;
        case 6:
                if (x-1>=0 && y-2>=0 && chess[x-1][y-2] == 0)
                {
                        *px = x - 1;
                        *py = y - 2;
                        return 1;
                }
                break;
        case 7:
                if (x-1>=0 && y+2<=Y-1 && chess[x-1][y+2] == 0)
                {
                        *px = x - 1;
                        *py = y + 2;
                        return 1;
                }
                break;
        }

        return 0;
}

int setHorse(int x, int y, int tag)
{
        int x1 = x, y1 = y, flag = 0, count = 0;

        // tag记录轨迹
        chess[x][y] = tag;
        // 如果tag等于64退出程序
        if (tag == X*Y)
        {
                return 1;
        }

        // 如果可以走，那么flag为1
        flag = next(&x1, &y1, count);
        // 否则尝试其他路径
        while (flag == 0 && count < 7)
        {
                count += 1;
                flag = next(&x1, &y1, count);
        }

        // 递归进入下一个坐标
        while (flag)
        {
                // 返回1表示成功找到落脚点
                if (setHorse(x1, y1, tag+1))
                {
                        return 1;
                }
                // 否则从上一步重新尝试
                x1 = x;
                y1 = y;
                count += 1;
                flag = next(&x1, &y1, count);
                while (flag == 0 && count < 7)
                {
                        count += 1;
                        flag = next(&x1, &y1, count);
                }
        }

        if (flag == 0)
        {
                chess[x][y] = 0;
        }

        return 0;
}

int main(void)
{
        int i, j;

        for (i = 0; i < X; i++)
        {
                for (j = 0; j < Y; j++)
                {
                        chess[i][j] = 0;
                }
        }

        // 讲道理，从 (2, 0) 坐标开始计算是比较容易出结果的
        // 如果你比较有耐心，或 CPU 特别强劲，可以尝试计算其它坐标
        if (setHorse(2, 0, 1))
        {
                for (i = 0; i < X; i++)
                {
                        for (j = 0; j < Y; j++)
                        {
                                printf("%02d  ", chess[i][j]);
                        }
                        putchar('\n');
                }
        }
        else
        {
                printf("可惜无解！\n");
        }

        return 0;
}

在setHOrse函数中while(flag) 迭代如果flag不为0则得到解，如果flag为0则退出循环，应该是无解，函数返回0，为什么中间要有一个

        if (flag == 0)
        {
                chess[x][y] = 0;
        }

并且当我删掉这段的时候，代码多次运行结果都为 无解？ 这段代码的作用是什么

永恒的蓝色梦想

领鱼币

xiaosi4081

领鱼币x2

lijiachen

正好缺鱼币

赚小钱

马走过的地方会被设置为1(二维数组上)，flag 表示能否找到，下一个位置，如果 flag 表示，在当前位置没有一个可以走的下一个位置，那么应该回退，此时，即表示当前的路是错的，所以应该在二维数组将当前位置设置为0

PS: 算法属于回溯算法。
回溯算法的核心思想是:
选择一个起点出发，沿着某一条路，不断检测是否可用，
如果可用就继续这条路(即深度遍历)
当遇到某种情况，可以确定，这条路行不通的时候，(剪枝函数)
就回头(回溯)，

quark

帮顶。。。