Javascript 递归回溯数独求解器

Question

我最近在此处的帮助下用 Golang 编写了相同的代码。

如果您熟悉 Go，可以在此处查看工作代码。

这是我在 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]
]

这是取自数独维基百科页面的网格。

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;
}

在回溯之前检查游戏是否已经解决解决了这个问题。在记录结果之前，它试图找到更多解决方案。

Javascript 递归回溯数独求解器

Javascript Recursive Backtracking Sudoku Solver

javascript

backtracking

sudoku

recursive-backtracking