数独求解器输出含无效零值，寻求技术排查帮助

我的数独求解器能尝试求解谜题，但输出结果中存在零值，不符合数独规则。我推测问题出在算法会将单元格的可行数值直接视为正确值，附上求解器完整代码，希望能帮忙测试并定位问题。预期输出应为不含零值的有效数独解。

export const initiate = (board) => {
    const updatedBoard = board.map((i) =>
        i.map((j) => (j === 0 ? (j = null) : j))
    );

    const validInput = validBoard(updatedBoard);
    if (!validInput) {
        return false;
    }

    return solve(updatedBoard);
};

const solve = (board) => {
    if (isSolved(board)) {
        return board;
    }

    const possibilities = findPossibilities(board);
    const validBoards = keepValid(possibilities);
    return searchForSolution(validBoards);
};

const searchForSolution = (boards) => {
    if (boards.length < 1) {
        return false;
    }

    const first = boards.shift();
    const tryPath = solve(first);
    if (tryPath) {
        return tryPath;
    }
    return searchForSolution(boards);
};

const isSolved = (board) => {
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === null) {
                return false;
            }
        }
    }
    return true;
};

const findPossibilities = (board) => {
    let res = [];
    const firstEmptySqr = findEmptySqr(board);
    if (firstEmptySqr !== undefined) {
        const y = firstEmptySqr[0];
        const x = firstEmptySqr[1];
        for (let i = 0; i <= 9; i++) {
            const newBoard = [...board];
            const row = [...newBoard[y]];
            row[x] = i;
            newBoard[y] = row;
            res.push(newBoard);
        }
    }

    return res;
};

const findEmptySqr = (board) => {
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === null) {
                return [i, j];
            }
        }
    }
};

const keepValid = (boards) => {
    let res = [];
    for (let i = 0; i < boards.length; i++) {
        if (validBoard(boards[i])) {
            res.push(boards[i]);
        }
    }
    return res;
};

const validBoard = (board) => {
    return rowsValid(board) && columnsValid(board) && boxesValid(board);
};

function rowsValid(board) {
    for (let i = 0; i < 9; i++) {
        let cur = [];
        for (let j = 0; j < 9; j++) {
            if (cur.includes(board[i][j])) {
                return false;
            } else if (board[i][j] !== null) {
                cur.push(board[i][j]);
            }
        }
    }
    return true;
}

function columnsValid(board) {
    for (let i = 0; i < 9; i++) {
        let cur = [];
        for (let j = 0; j < 9; j++) {
            if (cur.includes(board[j][i])) {
                return false;
            } else if (board[j][i] !== null) {
                cur.push(board[j][i]);
            }
        }
    }
    return true;
}

function boxesValid(board) {
    const boxCoordinates = [
        [0, 0],
        [0, 1],
        [0, 2],
        [1, 0],
        [1, 1],
        [1, 2],
        [2, 0],
        [2, 1],
        [2, 2],
    ];

    for (let y = 0; y < 9; y += 3) {
        for (let x = 0; x < 9; x += 3) {
            let cur = [];
            for (let i = 0; i < 9; i++) {
                let coordinates = [...boxCoordinates[i]];
                coordinates[0] += y;
                coordinates[1] += x;
                if (cur.includes(board[coordinates[0]][coordinates[1]])) {
                    return false;
                } else if (board[coordinates[0]][coordinates[1]] !== null) {
                    cur.push(board[coordinates[0]][coordinates[1]]);
                }
            }
        }
    }
    return true;
};

问题定位 #

1. 候选值范围错误：findPossibilities函数中，循环范围是0 <= i <=9，会将0作为候选值填入空单元格。虽然输入时把0转成了null，但这里又把0塞回棋盘，而数独的合法数字是1-9，0不属于有效数字。
2. 校验逻辑缺失数值范围检查：rowsValid、columnsValid、boxesValid只检查了数值重复，没有校验非null值是否在1-9范围内，导致含0的棋盘能通过校验，进入搜索流程。
3. 完成判断不检查数值合法性：isSolved仅检查是否存在null，不验证数值是否符合数独规则，导致含0的棋盘会被判定为已完成并返回。

修复方案 #

1. 修正候选值范围

修改findPossibilities的循环，只生成1-9的候选值：

const findPossibilities = (board) => {
    let res = [];
    const firstEmptySqr = findEmptySqr(board);
    if (firstEmptySqr !== undefined) {
        const y = firstEmptySqr[0];
        const x = firstEmptySqr[1];
        // 仅遍历1-9的合法数独数字
        for (let i = 1; i <= 9; i++) {
            const newBoard = [...board];
            const row = [...newBoard[y]];
            row[x] = i;
            newBoard[y] = row;
            res.push(newBoard);
        }
    }

    return res;
};

2. 补充数值范围校验（可选但推荐）

在各校验函数中增加数值范围检查，确保所有非null值都是1-9：

function rowsValid(board) {
    for (let i = 0; i < 9; i++) {
        let cur = [];
        for (let j = 0; j < 9; j++) {
            const val = board[i][j];
            if (val !== null) {
                // 检查数值是否在1-9范围内
                if (val < 1 || val > 9) {
                    return false;
                }
                if (cur.includes(val)) {
                    return false;
                }
                cur.push(val);
            }
        }
    }
    return true;
}

function columnsValid(board) {
    for (let i = 0; i < 9; i++) {
        let cur = [];
        for (let j = 0; j < 9; j++) {
            const val = board[j][i];
            if (val !== null) {
                if (val < 1 || val > 9) {
                    return false;
                }
                if (cur.includes(val)) {
                    return false;
                }
                cur.push(val);
            }
        }
    }
    return true;
}

function boxesValid(board) {
    const boxCoordinates = [
        [0, 0],
        [0, 1],
        [0, 2],
        [1, 0],
        [1, 1],
        [1, 2],
        [2, 0],
        [2, 1],
        [2, 2],
    ];

    for (let y = 0; y < 9; y += 3) {
        for (let x = 0; x < 9; x += 3) {
            let cur = [];
            for (let i = 0; i < 9; i++) {
                let coordinates = [...boxCoordinates[i]];
                coordinates[0] += y;
                coordinates[1] += x;
                const val = board[coordinates[0]][coordinates[1]];
                if (val !== null) {
                    if (val < 1 || val > 9) {
                        return false;
                    }
                    if (cur.includes(val)) {
                        return false;
                    }
                    cur.push(val);
                }
            }
        }
    }
    return true;
};

修复说明 #

修改候选值范围后，生成的所有候选棋盘都只会填入1-9的合法数字，从源头避免了零值的出现。补充数值范围校验则能进一步增强鲁棒性，防止其他异常输入或代码错误导致的非法数值进入求解流程。

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