[已解决]s1e36马踏棋问题

houqing1999

能否详细地解释一下马踏棋问题的求解步骤，例如定义的指针含义，所有if语句条件含义，while语句条件含义

#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;
}

最佳答案

月排行榜 / 总排行榜

陶远航

2023-6-3 20:53:40

这段代码是解决马踏棋盘问题的程序，其主要思路是通过递归的方式试图找到一条从初始位置开始覆盖所有棋盘格子的路径。下面对关键部分进行详细解释：

定义：

1. `int chess[X][Y]`：用来记录棋盘上每个位置是否被访问过的数组；
2. `int next(int *px, int *py, int count)`：用来确定马接下来应该走到哪个位置的函数；
3. `int setHorse(int x, int y, int tag)`：用来递归调用 next 函数，尝试所有的可能性，找到一条覆盖棋盘所有格子的路径，并将路径存储在 chess 数组中。

指针含义：

next 函数中传入的 px 和 py 分别表示当前马所在的位置，函数内部会根据计算出来的下一个可行位置更新 px 和 py 的值。

if 语句条件含义：

switch 语句中的 case 分支代表了八个方向，每个方向都有相应的 if 语句，其条件含义为：如果下一个可能走的位置（即棋盘上坐标为 (x+2, y-1)、(x+2, y+1)、(x+1, y-2) 等）未被访问过，则将 px 和 py 的值更新为该位置，并返回 1；否则返回 0。

while 语句条件含义：

1. 第一个 while 循环的条件为 flag == 0 && count < 7，其中 flag==0 表示当前方向上已经无法走下去了，需要尝试其他方向；count < 7 表示还有其他方向可以走（共八个方向），因此如果当前方向已经遍历完了，需要切换到下一个方向并重新尝试。
2. 第二个 while 循环的条件为 flag == 1，表示当前位置可以走，并且递归调用 setHorse 函数前往下一个位置。如果递归成功找到路径，立即返回 1；否则需要回溯到上一步，从其他方向继续尝试。

总体来说，该程序使用了深度优先搜索的思想，通过递归调用 setHorse 函数和 next 函数，不断试图寻找可行路径。当找到路径时，将其存储在 chess 数组中，最后输出即可得到一条解决马踏棋盘问题的路径。

跳转到最佳答案楼层

陶远航

币

sfqxx

占楼

sfqxx_小

isdkz

陶远航

这段代码是解决马踏棋盘问题的程序，其主要思路是通过递归的方式试图找到一条从初始位置开始覆盖所有棋盘格子的路径。下面对关键部分进行详细解释：

定义：

1. `int chess[X][Y]`：用来记录棋盘上每个位置是否被访问过的数组；
2. `int next(int *px, int *py, int count)`：用来确定马接下来应该走到哪个位置的函数；
3. `int setHorse(int x, int y, int tag)`：用来递归调用 next 函数，尝试所有的可能性，找到一条覆盖棋盘所有格子的路径，并将路径存储在 chess 数组中。

指针含义：

next 函数中传入的 px 和 py 分别表示当前马所在的位置，函数内部会根据计算出来的下一个可行位置更新 px 和 py 的值。

if 语句条件含义：

switch 语句中的 case 分支代表了八个方向，每个方向都有相应的 if 语句，其条件含义为：如果下一个可能走的位置（即棋盘上坐标为 (x+2, y-1)、(x+2, y+1)、(x+1, y-2) 等）未被访问过，则将 px 和 py 的值更新为该位置，并返回 1；否则返回 0。

while 语句条件含义：

1. 第一个 while 循环的条件为 flag == 0 && count < 7，其中 flag==0 表示当前方向上已经无法走下去了，需要尝试其他方向；count < 7 表示还有其他方向可以走（共八个方向），因此如果当前方向已经遍历完了，需要切换到下一个方向并重新尝试。
2. 第二个 while 循环的条件为 flag == 1，表示当前位置可以走，并且递归调用 setHorse 函数前往下一个位置。如果递归成功找到路径，立即返回 1；否则需要回溯到上一步，从其他方向继续尝试。

总体来说，该程序使用了深度优先搜索的思想，通过递归调用 setHorse 函数和 next 函数，不断试图寻找可行路径。当找到路径时，将其存储在 chess 数组中，最后输出即可得到一条解决马踏棋盘问题的路径。

isdkz

sfqxx_小 发表于 2023-6-3 20:53

老六

isdkz

[b]这个程序是求解国际象棋的“骑士巡逻”问题（Knight's Tour），在这个问题中，要找出骑士（棋盘上的马）可以如何走遍棋盘上的每一格而且每格只能走一次。

首先，我们先定义了一个8x8的二维数组 chess ，用来存储棋盘的状态。数组的元素值 chess[i][j] 表示棋子在第 i 行第 j 列的步骤数。开始时，所有的元素都被初始化为0，表示尚未走过。

接下来，定义了一个函数 next ，这个函数接收指向当前位置的指针，并根据 count 参数来确定骑士的下一个可能的移动方向。骑士的移动有8个可能的方向，用 count 从0到7来代表，然后用 switch 语句来实现。

然后是 setHorse 函数，这是主要的求解函数。它的输入是当前的位置 (x, y) 和当前的步数 tag 。然后它试图找到一个可走的下一步。如果找到，就递归调用自己，否则就尝试其他的方向。如果所有的方向都尝试过了都没有找到，就表示当前位置不可行，需要回溯到上一步，并将当前位置标记为未走过。

最后， main 函数首先将棋盘初始化，然后调用 setHorse 函数从位置(2, 0)开始寻找解。如果找到，就打印出来，否则打印“可惜无解”。

这个程序是典型的深度优先搜索（DFS）算法，它不断地尝试所有可能的走法，直到找到解或者所有可能的走法都已经尝试过。如果棋盘足够大，可能会需要花费相当长的时间来找到解。[/b]

houqing1999

isdkz 发表于 2023-6-3 20:55
这个程序是求解国际象棋的“骑士巡逻”问题（Knight's Tour），在这个问题中，要找出骑士（棋盘上的马）可 ...

谢谢