c - 为什么以下代码“"A knight' stour”无法正常工作？

Question

我正在 Codeblocks IDE 中使用 C 语言编写以下代码，尝试使用递归和回溯来解决骑士之旅问题。但问题是它会永远持续下去并且不会给出任何输出，尽管我认为这不是无限递归的情况。

#include <stdio.h>
#include <conio.h>
int board[8][8]= {{0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0}};
int i = 1;
int next(int a, int b);
int main()
{
    int  j, k;
    next(0,0);
    for(k = 0; k < 64; k++)
    {
        printf(" %d ", board[k/8][k%8]);
        if((i+1)%8==0)
            printf("\n");
    }
}
int next(int a, int b)
{
    if(i==64)
    {
        board[a][b]=64;
        return 1;
    }
    if((a<0||a>7||b<0||b>7))
        return 0;
    if(board[a][b]!=0)
        return 0;
        printf(" %d %d ", a, b);
         //getch();
    board[a][b]= i;
    if(next(a+2, b+1))
    {
        i++;
        return 1;
    }
    if(next(a+1, b+2))
    {
        i++;
        return 1;
    }
    if(next(a-1, b+2))
    {
        i++;
        return 1;
    }
    if(next(a+2, b-1))
    {
        i++;
        return 1;
    }
    if(next(a-2, b-1))
    {
        i++;
        return 1;
    }
    if(next(a-1, b-2))
    {
        i++;
        return 1;
    }
    if(next(a+1, b-2))
    {
        i++;
        return 1;
    }
    if(next(a-2, b+1))
    {
        i++;
        return 1;
    }
    board[a][b]=0;
    return 0;
}

Answer 1

您的主要问题是您使用全局变量来跟踪游览的长度，从而跟踪递归的深度。您只能递增此变量。

路径的长度应该是每个递归调用的变量，因此应该是 next 函数的本地变量。

(顺便说一下，对于全局变量来说，i 是一个可怕的名称。当你将其设置为本地变量时，这一点就会变得很清楚:打印棋盘的循环超过了k ，但是当您检查是否打印换行符时，您会测试 i。哎呀!)

测试棋盘是否已满可以通过两种方式进行:首先检查深度是否为 64，然后返回；不要赋值。 (更重要的是，因为您尚未确保 a 和 b 是有效的棋盘坐标。)第 64 次跳跃可能是非法的:访问 64 个方格的路径有一个长度为63，所以第64次跳转正好表明棋盘已满。

另一种方法是在检查平方是否有效后检查 i + 1 是否为 64。这相当于第一种方法，并且节省了一次调用。

通过这些更改，您的程序将变为:

#include <stdio.h>

#define N 8
#define NN (N*N)

int board[N][N]= {{0}};

int next(int a, int b, int i);

int main()
{
    int k;

    if (next(0, 0, 0)) {
        for(k = 0; k < NN; k++) {
            if(k && k % N == 0) puts("");
            printf(" %2d", board[k / N][k % N]);
        }
        puts("");
    } else {
        puts("No solution.");
    }

    return 0;
}

int next(int a, int b, int i)
{
    if (a < 0 || a >= N) return 0;
    if (b < 0 || b >= N) return 0;
    if (board[a][b] != 0) return 0;

    i++;
    board[a][b] = i;
    if (i == NN) return 1;

    if (next(a + 2, b + 1, i)) return 1;
    if (next(a + 1, b + 2, i)) return 1;
    if (next(a - 1, b + 2, i)) return 1;
    if (next(a + 2, b - 1, i)) return 1;
    if (next(a - 2, b - 1, i)) return 1;
    if (next(a - 1, b - 2, i)) return 1;
    if (next(a + 1, b - 2, i)) return 1;
    if (next(a - 2, b + 1, i)) return 1;

    board[a][b] = 0;
    return 0;
}

(专业提示:首先使用 N == 6 进行测试；暴力破解 8×8 板需要一些时间，在我的机器上大约需要三分钟。4×4 没有解决方案。)