Javascript Рекурсивный возврат судоку Солвер - PullRequest
Новая
       89

Javascript Рекурсивный возврат судоку Солвер

1 голос
/ 18 февраля 2020

Я недавно написал этот же код в Golang с некоторой помощью отсюда.

Если вы знакомы с go, вы можете увидеть рабочий код здесь.

Go Детская площадка

Вот что я пытаюсь сделать sh в python. Computerphile Video

Я сейчас пытаюсь перенести это на javascript.

Я инициализирую gameState. 

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 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()

1 Ответ

0 голосов
/ 19 февраля 2020

Спасибо @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;
}

Проверка того, была ли игра решена, до того, как обратный ход исправил эту проблему. Прежде чем регистрировать результаты, он пытался найти больше решений.

...