Javascript Откат в судоку Солвер не работает? - PullRequest
Новая
       81

Javascript Откат в судоку Солвер не работает?

0 голосов
/ 28 апреля 2020

Я пытаюсь внедрить решатель судоку с помощью Backtracking в Java Script, но он не работает для меня. Код возвращает ту же сетку судоку, которая была ему передана, скажите, пожалуйста, как это можно исправить. Созданный мною код можно найти ниже: - 

const grid = [
[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]
]


let solvedBoard = grid



// function for checking whether a number fits in the cell or not
const possible = (y,x,n) => {
    for(let i=0; i<9; i++){
        if (solvedBoard[y][i] == n){
            return false
        }
    }
    for(let i=0; i<9; i++){
        if (solvedBoard[i][x] == n){
            return false
        }
    }
    //fixed this in the code but still not solving
    x0 = Math.floor(x/3) * 3
    y0 = Math.floor(y/3) * 3
    for(let i=0; i<3; i++){
        for(let j=0; j<3; j++){
            if (solvedBoard[y0+i][x0+j] == n){
                return false
            }
        }
    }
    return true
}



//function for recursively solving the sudoku,
// this needs to be fixed
function solve(){
    for(let y=0;y<9;y++){
        for(let x=0;x<9;x++){
            if (solvedBoard[y][x] == 0){
                for(let n=0;n<10;n++){
                    if(possible(y,x,n)){
                        solvedBoard[y][x] = n
                        if(solve()){
                            return true
                        }
                        solvedBoard[y][x] = 0
                    }
                }
                return false
            }
        }
    }
}



function printGrid(grid) {
    var res = "";

    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            res += grid[i][j];
        }
        res += "\n";
    }
    console.log(res);
}

printGrid(gird)

console.log("************************")
console.log("Solved")
console.log("************************")

solve()
printGrid(solvedBoard)

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

РЕДАКТИРОВАТЬ: -

Измените функцию решить на эту, и приведенный выше код теперь должен работать правильно.

...