为什么以下 "A knight's tour" 的代码无法正常工作？

Question

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

#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，然后 return；不要赋值。（更重要的是，因为您没有确保 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 没有解决方案。）

为什么以下 "A knight's tour" 的代码无法正常工作？

Why is the following Code for "A knight's tour" not working properly?

c

backtracking

knights-tour