递归求解数独遇重复输入陷入无限循环的问题排查

核心问题：缺失初始输入合法性校验 #

你的递归函数solvePuzzle是默认「当前棋盘合法」才开始填数的，但如果输入本身就存在行/列/3×3宫的重复值，递归逻辑会直接卡死在「试填数字→发现冲突→回溯→再试→再回溯」的死循环里——因为初始状态就不合法，根本没解，而你的代码没提前做检查，导致递归一直在第一行附近打转，栈根本推进不了。

为什么会无限循环？ #

举个例子：如果某行已经有两个5，递归到该行的空位置时，试遍1-9都会发现冲突（要么行重复，要么列/宫重复），于是回溯到上一层。但上一层处理的也是有冲突的行，同样找不到合法数字，就这么来回折腾，无限递归下去。

怎么解决？ #

在调用递归函数之前，先给整个棋盘做一次全局合法性检查，确认所有已填数字都符合数独规则。如果初始输入就不合法，直接返回求解失败，别让递归跑起来。

合法性检查函数示例 #

bool isBoardValid(vector<vector<int>>& board) {
    // 检查每一行
    for (int i = 0; i < 9; ++i) {
        bool used[10] = {false};
        for (int j = 0; j < 9; ++j) {
            int num = board[i][j];
            if (num == 0) continue;
            if (used[num]) return false;
            used[num] = true;
        }
    }
    // 检查每一列
    for (int j = 0; j < 9; ++j) {
        bool used[10] = {false};
        for (int i = 0; i < 9; ++i) {
            int num = board[i][j];
            if (num == 0) continue;
            if (used[num]) return false;
            used[num] = true;
        }
    }
    // 检查每个3×3宫
    for (int box = 0; box < 9; ++box) {
        bool used[10] = {false};
        int startRow = (box / 3) * 3;
        int startCol = (box % 3) * 3;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                int num = board[startRow + i][startCol + j];
                if (num == 0) continue;
                if (used[num]) return false;
                used[num] = true;
            }
        }
    }
    return true;
}

修改主调用逻辑 #

在启动递归前先做检查：

if (!isBoardValid(board)) {
    cout << "输入数独本身不合法，无解" << endl;
    return false;
}
return solvePuzzle(board);

额外优化提醒 #

另外确认下你递归里的isValid函数逻辑是否正确——每次试填数字前，要检查该数字在当前行、列、宫是否唯一，避免无效的递归尝试。比如这个实现：

bool isValid(vector<vector<int>>& board, int row, int col, int num) {
    // 检查当前行
    for (int j = 0; j < 9; ++j) {
        if (board[row][j] == num) return false;
    }
    // 检查当前列
    for (int i = 0; i < 9; ++i) {
        if (board[i][col] == num) return false;
    }
    // 检查当前3×3宫
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[startRow + i][startCol + j] == num) return false;
        }
    }
    return true;
}

这样不管是初始输入有问题，还是递归中试填的数字不合法，都能及时终止无效流程，不会再出现无限循环。

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