骑士巡游回溯算法：返回最大可行移动次数问题求助

你的核心需求是让骑士巡游算法返回最大可行移动对应的访问格子数（N=3时应为8），而非仅判断是否存在完整巡游路径。当前代码存在以下关键问题：

1. 骑士移动数组错误：yMove[7]的值应为-1而非-2，导致遗漏了合法的骑士移动（x+2, y-1），同时包含了无效移动。
2. 递归逻辑错误：原代码仅在找到完整巡游时返回1，否则无有效返回（注释了return 0），且未跟踪所有路径的最大访问格子数。
3. 无效参数冗余：plays参数设计错误，无法正确统计移动次数，实际movei已可直接反映访问的格子数。

修正后的完整代码 #

#include <stdio.h>
#define N 3

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[], int yMove[]);

int isSafe(int x, int y, int sol[N][N])
{
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void printSolution(int sol[N][N])
{
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++)
            printf(" %2d ", sol[x][y]);
        printf("\n");
    }
}

void solveKT()
{
    int sol[N][N];

    // 初始化路径矩阵，-1表示未访问
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            sol[x][y] = -1;

    sol[0][0] = 0; // 骑士初始位置标记为第0步

    // 修正后的8种骑士移动方向
    int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

    // 计算并输出结果
    int max_squares = solveKTUtil(0, 0, 1, sol, xMove, yMove);
    printf("最大访问格子数: %d\n", max_squares);
    printf("最大移动次数: %d\n", max_squares - 1);
    printSolution(sol);
}

// 递归函数：返回从当前位置出发能访问的最大格子数
int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[], int yMove[])
{
    int max_count = movei; // 当前已访问的格子数作为初始最大值

    // 若已访问所有格子，直接返回总数
    if (movei == N * N) {
        return max_count;
    }

    // 尝试所有8种移动方向
    for (int k = 0; k < 8; k++) {
        int next_x = x + xMove[k];
        int next_y = y + yMove[k];

        if (isSafe(next_x, next_y, sol)) {
            sol[next_x][next_y] = movei; // 标记当前格子为已访问

            // 递归探索后续路径，获取该路径的最大访问数
            int current_result = solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove);

            // 更新最大值
            if (current_result > max_count) {
                max_count = current_result;
            }

            sol[next_x][next_y] = -1; // 回溯：取消标记
        }
    }

    return max_count;
}

int main()
{
    solveKT();
    return 0;
}

关键修正说明 #

1. 修正移动方向数组：将yMove[7]从-2改为-1，确保覆盖所有8种合法的骑士移动方式。
2. 重构递归逻辑：
   • 递归函数返回从当前位置出发能访问的最大格子数，而非仅判断是否存在完整路径。
   • 对每个合法移动，递归探索后续路径并更新最大值，最后回溯取消格子标记。
3. 移除冗余参数：删除无效的plays参数，利用movei直接统计已访问的格子数（初始值为1，对应初始位置的1个格子）。
4. 明确输出含义：分别打印最大访问格子数和最大移动次数（移动次数=格子数-1），符合你对N=3返回8的需求。

内容的提问来源于stack exchange，提问作者BigFoot Programmer