我的C语言骑士巡游问题程序陷入无限递归，请求排查

问题描述 #

我之前写过类似骑士巡游的程序，想尽量少改代码适配骑士巡游问题，但运行后无任何输出，递归看似陷入无限循环（测试跑了3分钟还没结果，正常应该1-2秒出结果）。网上的同类程序原理看起来和我一致，但找不到问题所在。以下是我的代码：

#include <stdio.h>
#include <stdlib.h>

#define SIDE 8
#define VISITED 1
#define NOT_VISITED 0

#define FALSE 0
#define TRUE !FALSE

void printBoard(int board[][SIDE]);
int goHorsie(int board[][SIDE], int x, int y, int step);

int main(void)
{
    int board[SIDE][SIDE] = { NOT_VISITED };
    if (goHorsie(board, 0, 0, 1))
    {
        printf("Yes, the knight's tour problem is possible, here is the result:\n");
        printBoard(board);
    }
    else
    {
        printf("No, the knight's tour problem is not possible.\n");
    }
    return 0;
}


/*
检查骑士能否遍历整个棋盘且每个格子仅踩一次
输入：棋盘、当前位置坐标(x,y)、当前步数
输出：是否找到有效路径
*/
int goHorsie(int board[][SIDE], int x, int y, int step)
{
    int res = FALSE;

    if (step == (SIDE * SIDE + 1))
    {
        res = TRUE;
    }
    else if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || // 超出棋盘范围
        board[x][y] != NOT_VISITED) // 已访问过该格子
    {
        res = FALSE;
    }
    else
    {
        board[x][y] = step;
        step++;

        // 改变顺序会改变路径，因为只要有一个分支返回TRUE，后续分支不会执行
        res = goHorsie(board, x + 2, y + 1, step) ||
            goHorsie(board, x + 2, y - 1, step) ||
            goHorsie(board, x + 1, y + 2, step) ||
            goHorsie(board, x + 1, y - 2, step) ||
            goHorsie(board, x - 2, y + 1, step) ||
            goHorsie(board, x - 2, y - 1, step) ||
            goHorsie(board, x - 1, y + 2, step) ||
            goHorsie(board, x - 1, y - 2, step);

        if (!res)
        {
            board[x][y] = NOT_VISITED;
        }
    }

    return res;
}


/*
打印棋盘
输入：待打印的棋盘
输出：无
*/
void printBoard(int board[][SIDE])
{
    int i = 0, j = 0;

    for (i = 0; i < SIDE; i++)
    {
        for (j = 0; j < SIDE; j++)
        {
            printf("%3d", board[i][j]);
        }
        printf("\n"); // 换行
    }
}

问题根源 #

代码逻辑本身是正确的，但固定的递归方向顺序导致搜索效率极低。从(0,0)出发按当前顺序尝试移动时，程序会优先进入大量无效路径，触发指数级的回溯操作，导致搜索时间极长，看起来像无限循环。

最小改动的解决方案 #

引入Warnsdorff规则（优先选择下一步可移动位置最少的方向），仅需修改goHorsie函数及新增少量辅助函数，就能大幅提升搜索效率。修改后的完整核心代码如下（其余代码保持不变）：

// 全局定义骑士的8个移动方向
int dx[] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[] = {1, -1, 2, -2, 1, -1, 2, -2};

// 统计某位置的可移动步数
int countMoves(int board[][SIDE], int x, int y) {
    int count = 0;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < SIDE && ny >= 0 && ny < SIDE && board[nx][ny] == NOT_VISITED) {
            count++;
        }
    }
    return count;
}

// 按Warnsdorff规则排序移动方向（可移动步数少的在前）
void sortDirections(int board[][SIDE], int x, int y, int dirs[]) {
    for (int i = 0; i < 7; i++) {
        for (int j = i + 1; j < 8; j++) {
            // 计算两个方向对应位置的可移动步数
            int nx1 = x + dx[dirs[i]];
            int ny1 = y + dy[dirs[i]];
            int c1 = (nx1 >= 0 && nx1 < SIDE && ny1 >= 0 && ny1 < SIDE && board[nx1][ny1] == NOT_VISITED) 
                     ? countMoves(board, nx1, ny1) : 9; // 无效位置设为大数

            int nx2 = x + dx[dirs[j]];
            int ny2 = y + dy[dirs[j]];
            int c2 = (nx2 >= 0 && nx2 < SIDE && ny2 >= 0 && ny2 < SIDE && board[nx2][ny2] == NOT_VISITED) 
                     ? countMoves(board, nx2, ny2) : 9;

            // 按步数从小到大排序
            if (c1 > c2) {
                int temp = dirs[i];
                dirs[i] = dirs[j];
                dirs[j] = temp;
            }
        }
    }
}

int goHorsie(int board[][SIDE], int x, int y, int step)
{
    int res = FALSE;

    if (step == (SIDE * SIDE + 1))
    {
        res = TRUE;
    }
    else if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || 
        board[x][y] != NOT_VISITED)
    {
        res = FALSE;
    }
    else
    {
        board[x][y] = step;
        step++;

        // 存储方向索引，用于排序
        int dirs[] = {0,1,2,3,4,5,6,7};
        // 按Warnsdorff规则排序移动方向
        sortDirections(board, x, y, dirs);

        // 按排序后的顺序尝试移动
        for (int i = 0; i < 8; i++) {
            int d = dirs[i];
            if (goHorsie(board, x + dx[d], y + dy[d], step)) {
                res = TRUE;
                break;
            }
        }

        if (!res)
        {
            board[x][y] = NOT_VISITED;
        }
    }

    return res;
}

验证结果 #

修改后，程序会在1-2秒内输出骑士巡游的完整路径，彻底解决原程序超时的问题。

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