Java递归回溯数独求解器

Question

我最近在这里得到了一些帮助，用Golang编写了相同的代码。

如果您熟悉go，可以在这里查看工作代码。

Go Playground

这是我要在python中完成的工作。Computerphile Video

我现在正尝试将其移植到javascript。

我初始化游戏状态。

var gameState = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

这是来自数独Wikipedia页面的网格。

Sudoku Wiki

我编写了以下辅助函数，以获取网格上任何位置的行，列和块单元。我已经对它们全部进行了测试，它们似乎都可以正常工作。

function isUnitUnique(unit) {
    for (let value = 1; value <= 9; value++) {
        let tally = 0;
        for (let index = 0; index < 9; index++) {
            if (unit[index] == value) {
                tally++;
            }
        }
        if (tally > 1) {
            return false;
        }
    }
    return true;
}
function getColumnUnit(board, column) {
    let unit = [];
    for (let row = 0; row < 9; row++) {
        unit.push(board[row][column]);
    }
    return unit;
}
function getBlockUnit(board, x, y) {
    let unit = []
    if (x >= 0 && x <= 2) { j = 1; }
    else if (x >= 3 && x <= 5) { j = 4; }
    else if (x >= 6 && x <= 8) { j = 7; }
    if (y >= 0 && y <= 2) { i = 1; }
    else if (y >= 3 && y <= 5) { i = 4; }
    else if (y >= 6 && y <= 8) { i = 7; }
    unit.push(board[i - 1][j - 1]);
    unit.push(board[i - 1][j]);
    unit.push(board[i - 1][j + 1]);
    unit.push(board[i][j - 1]);
    unit.push(board[i][j]);
    unit.push(board[i][j + 1]);
    unit.push(board[i + 1][j - 1]);
    unit.push(board[i + 1][j]);
    unit.push(board[i + 1][j + 1]);
    return unit;
}

然后，我将辅助函数与以下代码结合使用，以尝试解决难题。这是一种递归回溯算法。

function solve() {
    for (let row = 0; row < 9; row++) {
        for (let column = 0; column < 9; column++) {
            if (gameState[row][column] == 0) {
                for (let value = 1; value <= 9; value++) {
                    if (possible(row, column, value)) {
                        gameState[row][column] = value;
                        solve();
                        gameState[row][column] = 0;
                    }
                }
                return;
            }
        }
    }
    console.log(gameState);
    return;
}
function possible(y, x, n) {
    let boardCopy = JSON.parse(JSON.stringify(gameState));
    boardCopy[y][x] = n;
    return isUnitUnique(boardCopy[y]) && isUnitUnique(getColumnUnit(boardCopy, x)) && isUnitUnique(getBlockUnit(boardCopy, x, y))
}

此控制台记录的初始游戏状态保持不变。通过进行一些调试，我可以看到算法正在通过网格，但是它似乎并没有保留我对网格所做的更改。

提前感谢。

正如这里所建议的，是我代码的可运行版本。当我在代码段中运行它时，它可以工作。使用chrome时不会。

var gameState = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]
function solve() {
    for (let row = 0; row < 9; row++) {
        for (let column = 0; column < 9; column++) {
            if (gameState[row][column] == 0) {
                for (let value = 1; value <= 9; value++) {
                    if (possible(row, column, value)) {
                        gameState[row][column] = value;
                        solve();
                        gameState[row][column] = 0;
                    }
                }
                return;
            }
        }
    }
    console.log(gameState);
    return;
}
function possible(y, x, n) {
    let boardCopy = JSON.parse(JSON.stringify(gameState));
    boardCopy[y][x] = n;
    return isUnitUnique(boardCopy[y]) && isUnitUnique(getColumnUnit(boardCopy, x)) && isUnitUnique(getBlockUnit(boardCopy, x, y))
}
function isUnitUnique(unit) {
    for (let value = 1; value <= 9; value++) {
        let tally = 0;
        for (let index = 0; index < 9; index++) {
            if (unit[index] == value) {
                tally++;
            }
        }
        if (tally > 1) {
            return false;
        }
    }
    return true;
}
function getColumnUnit(board, column) {
    let unit = [];
    for (let row = 0; row < 9; row++) {
        unit.push(board[row][column]);
    }
    return unit;
}
function getBlockUnit(board, x, y) {
    let unit = []
    if (x >= 0 && x <= 2) { j = 1; }
    else if (x >= 3 && x <= 5) { j = 4; }
    else if (x >= 6 && x <= 8) { j = 7; }
    if (y >= 0 && y <= 2) { i = 1; }
    else if (y >= 3 && y <= 5) { i = 4; }
    else if (y >= 6 && y <= 8) { i = 7; }
    unit.push(board[i - 1][j - 1]);
    unit.push(board[i - 1][j]);
    unit.push(board[i - 1][j + 1]);
    unit.push(board[i][j - 1]);
    unit.push(board[i][j]);
    unit.push(board[i][j + 1]);
    unit.push(board[i + 1][j - 1]);
    unit.push(board[i + 1][j]);
    unit.push(board[i + 1][j + 1]);
    return unit;
}
solve()

Answer 1

感谢@HereticMonkey建议我使用堆栈代码段共享我的代码。通过这样做，我意识到它可以在这种环境下工作，并且与在引起问题的浏览器（Chrome）中运行代码有关。也要感谢@ bcr666，他也提到该算法可能在返回的过程中将自身清零。

问题中列出的代码都是正确的。我添加了一项检查，以防止该函数在达到退出条件后继续执行。

let solved = false
function solve() {
    for (let row = 0; row < 9; row++) {
        for (let column = 0; column < 9; column++) {
            if (gameState[row][column] == 0) {
                for (let value = 1; value <= 9; value++) {
                    if (possible(row, column, value)) {
                        gameState[row][column] = value;
                        solve();
                        if (!solved) {
                            gameState[row][column] = 0;
                        }
                    }
                }
                return;
            }
        }
    }
    solved = true;
    console.log(gameState);
    return;
}

[在回溯之前检查游戏是否已解决，解决了此问题。