4x4数独求解函数遇Javascript - Too much recursion错误求助

问题根源分析 #

1. 递归滥用：你的isSafeRow、isSafeColumn在检测到数字冲突时直接调用solverFor4x4，导致函数无限嵌套调用，瞬间触发递归栈溢出。合法性校验函数的唯一职责应该是返回布尔值，判断当前数字能否放在目标位置，而非主动启动求解。
2. 求解逻辑缺失：原函数只是随机生成一个数字填充所有可填位置，没有数独求解必备的回溯逻辑——当当前选择导致后续无法填充时，需要回退上一步的选择，尝试其他数字。
3. 辅助函数漏洞：isSafeColumn里循环变量覆盖了参数i，导致列校验逻辑错误；isSafeArea未实现2x2区块的合法性校验，这会导致填充的数字违反数独规则。

修正后的完整代码 #

// 4x4数独求解主函数，使用回溯法
function solverFor4x4(grid) {
    // 找到第一个空白格（值为0）
    const emptyCell = findEmptyCell(grid);
    if (!emptyCell) {
        // 没有空白格，求解完成
        showSolution(grid);
        return true;
    }

    const [row, col] = emptyCell;
    // 尝试1-4的数字
    for (let num = 1; num <= 4; num++) {
        if (isSafe(grid, num, row, col)) {
            // 放置数字
            grid[row][col] = num;
            // 递归求解剩余格子，成功则返回true
            if (solverFor4x4(grid)) {
                return true;
            }
            // 回溯：当前数字导致后续无解，撤销选择
            grid[row][col] = 0;
        }
    }
    // 所有数字都尝试过，无解
    return false;
}

// 寻找第一个空白格
function findEmptyCell(grid) {
    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < 4; j++) {
            if (grid[i][j] === 0) {
                return [i, j];
            }
        }
    }
    return null;
}

// 校验数字是否可以放在目标位置
function isSafe(grid, num, row, col) {
    return isSafeRow(grid, num, row) &&
           isSafeColumn(grid, num, col) &&
           isSafeArea(grid, num, row, col);
}

// 行校验：当前行是否已有该数字
function isSafeRow(grid, num, row) {
    return !grid[row].includes(num);
}

// 列校验：当前列是否已有该数字
function isSafeColumn(grid, num, col) {
    for (let i = 0; i < 4; i++) {
        if (grid[i][col] === num) {
            return false;
        }
    }
    return true;
}

// 2x2区块校验：当前区块是否已有该数字
function isSafeArea(grid, num, row, col) {
    // 计算区块的起始行和列（4x4分为2x2区块）
    const blockRowStart = Math.floor(row / 2) * 2;
    const blockColStart = Math.floor(col / 2) * 2;

    for (let i = blockRowStart; i < blockRowStart + 2; i++) {
        for (let j = blockColStart; j < blockColStart + 2; j++) {
            if (grid[i][j] === num) {
                return false;
            }
        }
    }
    return true;
}

// 示例：展示求解结果
function showSolution(grid) {
    console.log("数独求解结果：");
    grid.forEach(row => console.log(row.join(" ")));
}

// 测试用例
const testGrid = [
    [1, 0, 3, 0],
    [0, 2, 0, 4],
    [3, 0, 1, 0],
    [0, 4, 0, 2]
];
solverFor4x4(testGrid);

关键优化点 #

• 回溯法核心逻辑：找到空白格后尝试1-4的数字，合法则递归求解，失败则回退，这是数独求解的标准高效思路，避免了随机尝试的盲目性。
• 合法性校验回归本职：所有校验函数仅返回布尔值，不再触发递归，彻底解决递归栈溢出问题。
• 完善区块校验：实现了4x4数独必备的2x2区块合法性检查，确保求解结果符合规则。

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