Алгоритм рекурсивного возврата в JavaScript - PullRequest
Новая
       80

Алгоритм рекурсивного возврата в JavaScript

0 голосов
/ 27 апреля 2018

Я сейчас пытаюсь узнать об алгоритмах возврата и работаю над игрой судоку. Я понимаю основы работы алгоритма и с его помощью написал решатель судоку.

Моя текущая проблема связана с удалением заданного количества чисел из заполненной сетки Судоку для создания действительного Судоку с уникальным решением.

Я проверил подобные вопросы здесь, но не нашел ответов.

Вот пример решенной решетки Судоку: 

solvedSudokuGrid = 
[["8","6","1","3","4","2","9","5","7"],
 ["2","5","3","8","7","9","4","6","1"],
 ["4","9","7","6","5","1","2","3","8"],
 ["6","7","2","5","1","8","3","9","4"],
 ["9","1","4","7","2","3","6","8","5"],
 ["5","3","8","4","9","6","7","1","2"],
 ["3","4","6","2","8","5","1","7","9"],
 ["7","8","9","1","3","4","5","2","6"],
 ["1","2","5","9","6","7","8","4","3"]];

Вот функция для удаления установленного количества чисел из сетки: 

function removeNrs(grid, nrsToBeRemoved) {
    //check if enough numbers have been removed
    if (nrsToBeRemoved <= 0) {
    return true;
    }
    //find the next random full cell and set the grid to "" on that cell to remove a number
    var nextNr = shuffle(findFullCells(grid))[0];
    var row = nextNr[0];
    var column = nextNr[1];
    var value = grid[row][column];
    grid[row][column] = "";
    nrsToBeRemoved--;
    //check if the sudoku grid has only 1 solution if yes start recursion
    if (countAllSolutions(grid) < 2){
        if(removeNrs(grid, nrsToBeRemoved)){
            return grid;
            }
        }
    //if the sudoku grid has more than 1 possible solution return the grid to the previous state and backtrack
    grid[row][column] = value;
    return false;
}

Вот проблема: если я ввожу небольшое количество цифр для удаления, функция работает. например: 

removeNrs(solvedSudokuGrid, 5); //returns a valid grid

Если я введу большее количество цифр, которые будут удалены, функция просто вернет false. например: 

removeNrs(solvedSudokuGrid, 50); //returns false

Из основной отладки, которую я попробовал, я вижу, что функция работает до тех пор, пока ей не нужно возвращаться назад. Если функция должна вернуться назад, она, похоже, вернется полностью к началу и завершит работу с исходной сеткой, а затем вернет false.

Любая помощь, объяснения или вещи для чтения очень ценятся.

Edit:

https://jsfiddle.net/mg57u0mv/

Вот полный код, но некоторые имена функций и переменных были изменены, чтобы лучше соответствовать всему коду. 

    function createTable() {
        var tbl = document.createElement("table");
        var tbdy = document.createElement("tbody");
        for (var row = 0; row < 9; row++) {
            var tr = document.createElement("tr");
            for (var column = 0; column < 9; column++) {
                var td = document.createElement("td");
                var input = document.createElement("input");
                input.type = "text";
                input.id = "r"+row+"c"+column;
                input.className = "grid-inputs grid-inputs-row-" + row;
                //input.placeholder = "[" + row + " , " + column + "]";
                //input.placeholder = input.id;
                if ((row+1) % 3 === 0) {
                    td.style.borderBottom = "3px solid black";
                }
                if ((column+1) % 3 === 0) {
                    td.style.borderRight = "3px solid black";
                }
                tr.appendChild(td);
                td.appendChild(input);
            }
            tbdy.appendChild(tr);
        }
        tbl.appendChild(tbdy);
        document.body.appendChild(tbl);
    }

    function createButton(text, func) {
        var button = document.createElement("button");
        var t = document.createTextNode(text);
        button.onclick = func;
        button.appendChild(t);
        document.body.appendChild(button);
    }

    function shuffle(array) {
        var counter = array.length;
        var temp, index;
        while (counter) {
            index = Math.floor(Math.random() * counter);
            counter--;
            temp = array[counter];
            array[counter] = array[index];
            array[index] = temp;
        }
        return array;
    }

    function retrieveGrid() {
        var result = [];
        var rowContents = [];
        for (var row = 0; row < 9; row++) {
            for (var column = 0; column < 9; column++) {
                rowContents.push(document.getElementsByClassName("grid-inputs-row-"+row)[column].value);
            }
            result.push(rowContents);
            rowContents = [];
        }
        return result;
    }

    function printGrid(grid) {
        for (var row = 0; row < 9; row++) {
            for (var column = 0; column < 9; column++) {
                document.getElementsByClassName("grid-inputs-row-"+row)[column].value = grid[row][column];
            }
        }
    }

    function checkRowColumnBlock(grid, row, column, value) {
    //create row, column and block lists to be checked for doubles
        var rowList =  grid[row];
        var columnList = [];
        for (var columnCounter = 0; columnCounter < 9; columnCounter++) {
            columnList.push(grid[columnCounter][column]);
        }
        var blockList = [];
        for (var startRow = Math.floor(row/3) * 3, endRow = startRow + 3; startRow < endRow; startRow++) {
            for (var startColumn = Math.floor(column/3) * 3, endColumn = startColumn + 3; startColumn < endColumn; startColumn++) {
                blockList.push(grid[startRow][startColumn]);
            }
        }
    //check row, column and block list for value
        if (rowList.indexOf(value.toString()) === -1 &&
            columnList.indexOf(value.toString()) === -1 &&
            blockList.indexOf(value.toString()) === -1) {
            return true;
        } else {
            return false;
        }
    }

    function checkGrid(grid) {
        for (var row = 0; row < 9; row++) {
            for (var column = 0; column < 9; column++) {
                if (grid[row][column] !== "") {
                    var value = grid[row][column];
                    grid[row][column] = "";
                    if (!checkRowColumnBlock(grid, row, column, value)) {
                        console.log("Invalid Grid");
                        return false;
                    }
                    grid[row][column] = value;
                }
            }
        }
        console.log("Valid Grid");
        return true;
    }

    function findEmptyCells(grid) {
        var result = [];
        for (var row = 0; row < 9; row++){
            for (var column = 0; column < 9; column++) {
                if (grid[row][column] === "") {
                    result.push([row , column]);
                }
            }
        }
        if (result.length == 0) {
            result = false;
        }
        return result;
    }

    function sortPossibilties(grid) {
        var result = [];
        var listOfEmptyCells = findEmptyCells(grid);
        if (listOfEmptyCells === false) {
            return false;
        }
        var listOfPossibilities = findPossibilitiesForGrid(grid);
        var counter = listOfEmptyCells.length;
        for (var cell = 0; cell < counter; cell++) {
            result.push({"cell": listOfEmptyCells[cell], "possibilities": listOfPossibilities[cell]});
        }
        result.sort(function (first, second) {
        return first.possibilities.length - second.possibilities.length;
        });

        return result;
    }

    function findNextEmptyCell(grid) {
        var sortedEmptyCells = sortPossibilties(grid);
        if (sortedEmptyCells === false) {
            return false;
        }
            return sortedEmptyCells[0];
    }

    function findFullCells(grid) {
        var result = [];
        for (var row = 0; row < 9; row++){
            for (var column = 0; column < 9; column++) {
                if (grid[row][column] !== "") {
                    result.push([row , column]);
                }
            }
        }
        if (result.length == 0) {
            result = false;
        }
        return result;
    }

    function findRandomFullCell(listOfFullCells) {
        if (listOfFullCells === false) {
            return false;
        }
        var result = listOfFullCells[Math.floor(Math.random() * listOfFullCells.length)];
        return result;
    }

    function createEmptyGrid() {
    //create grid 9x9 fill with blankspace
        var grid = [];
        for (var gridCounter = 0; gridCounter < 9; gridCounter++) {
            grid.push(new Array(9).fill(""));
        }
        return grid;
    }

    function createIncRandomGrid(numberOfRandomCells) {
        var grid = createEmptyGrid();
        for (var counter = 0; counter < numberOfRandomCells; counter++) {
            grid[Math.floor(Math.random() * 9)][Math.floor(Math.random() * 9)] =
            Math.floor(Math.random() * 9 + 1).toString();
        }
        return grid;
    }


    function createCorRandomGrid(numberOfRandomCells) {
        var grid;
        do {grid = createIncRandomGrid(numberOfRandomCells);}
        while (checkGrid(grid) === false);
        return grid;
    }

    function findPossibilitiesForCell(grid, row, column) {
        var possibilities = [];
        for (var value = 1; value < 10; value++) {
            if (checkRowColumnBlock(grid, row, column, value)) {
                possibilities.push(value.toString());
            }
        }
        return possibilities;
    }

    function findPossibilitiesForGrid(grid) {
        var result = [];
        var listOfEmptyCells = findEmptyCells(grid);
        var amountOfEmptyCells = listOfEmptyCells.length;
        for (var cell = 0; cell < amountOfEmptyCells; cell++) {
            var row = listOfEmptyCells[cell][0];
            var column = listOfEmptyCells[cell][1];
            result.push(findPossibilitiesForCell(grid, row, column));

        }
        return result;
    }

    function solveSudoku(grid) {
        var emptyCell = findNextEmptyCell(grid);
        if (emptyCell === false) {
            return true;
        }
        var row = emptyCell.cell[0];
        var column = emptyCell.cell[1];
        var valueList = shuffle(emptyCell.possibilities);
        var valueListLength = valueList.length;
        for (var valueIndex = 0; valueIndex < valueListLength; valueIndex++) {
            if (checkRowColumnBlock(grid, row, column, valueList[valueIndex])) {
                grid[row][column] = valueList[valueIndex].toString();
                if (solveSudoku(grid)) {
                    return grid;
                }
                grid[row][column] = "";
            }
        }
        return false;
    }

    function countAllSolutions(grid) {
        var nrOfSolutions = 1;
        function solveAll(grid) {
            var emptyCell = findNextEmptyCell(grid);
            if (emptyCell === false || nrOfSolutions > 1) {
                return true;
            }
            var row = emptyCell.cell[0];
            var column = emptyCell.cell[1];
            var valueList = shuffle(emptyCell.possibilities);
            var valueListLength = valueList.length;
            for (var valueIndex = 0; valueIndex < valueListLength; valueIndex++) {
                if (checkRowColumnBlock(grid, row, column, valueList[valueIndex])) {
                    grid[row][column] = valueList[valueIndex].toString();
                    if (solveAll(grid)) {
                        nrOfSolutions++;
                    }
                    grid[row][column] = "";
                }
            }
            return false;
        }
        solveAll(grid);
        return nrOfSolutions-1;
    }

    function findPossibilitiesForFullCell(grid, row, column) {
        var possibilities = [];
        var originalValue = grid[row][column];
        grid[row][column] = "";
        for (var value = 1; value < 10; value++) {
            if (checkRowColumnBlock(grid, row, column, value)) {
                possibilities.push(value.toString());
            }
        }
        grid[row][column] = originalValue;
        return possibilities;
    }

    function findPossibilitiesForFullGrid(grid) {
        var result = [];
        var listOfFullCells = findFullCells(grid);
        var amountOfFullCells = listOfFullCells.length;
        for (var cell = 0; cell < amountOfFullCells; cell++) {
            var row = listOfFullCells[cell][0];
            var column = listOfFullCells[cell][1];
            result.push(findPossibilitiesForFullCell(grid, row, column));

        }
        return result;
    }

    function sortFullCells(grid) {
        var result = [];
        var listOfFullCells = findFullCells(grid);
        if (listOfFullCells === false) {
            return false;
        }
        var listOfPossibilities = findPossibilitiesForFullGrid(grid);
        var counter = listOfFullCells.length;
        for (var cell = 0; cell < counter; cell++) {
            result.push({"cell": listOfFullCells[cell], "possibilities": listOfPossibilities[cell]});
        }
        result.sort(function (first, second) {
        return first.possibilities.length - second.possibilities.length;
        });
        return result;
    }


    function findNextFullCells(grid) {
        var sortedFullCells = sortFullCells(grid);
        if (sortedFullCells === false) {
            return false;
        }
        var result = [];
        result.push(sortedFullCells[0]);
        for (var cell = 1, length = sortedFullCells.length; cell < length; cell++){
            if(sortedFullCells[cell].possibilities.length === sortedFullCells[0].possibilities.length) {
                result.push(sortedFullCells[cell]);
            }
        }
        return result;
    }


    function removeCells(grid, cellsToBeRemoved) {
        if (cellsToBeRemoved <= 0) {
            return grid;
        }
        var nextCell = shuffle(findFullCells(grid))[0];
        var row = nextCell[0];
        var column = nextCell[1];
        var value = grid[row][column];
        grid[row][column] = "";
        cellsToBeRemoved--;
        if (countAllSolutions(grid) < 2) {
            grid = removeCells(grid, cellsToBeRemoved);
            return grid;
        } else {
            grid[row][column] = value;
            grid = removeCells(grid, cellsToBeRemoved);
        }
        return grid;
    }

    createTable();

    createButton("Solve Sudoku", function () {
        console.time("Solved");
        printGrid(solveSudoku(retrieveGrid()));
        console.timeEnd("Solved");
    });

    createButton("Remove Cells", function () {
        console.time("Removed");
        printGrid(removeCells(retrieveGrid(),55));
        console.timeEnd("Removed");
    });

    createButton("Count Solutions", function () {
        console.time("Counting");
        console.log(countAllSolutions(retrieveGrid()));
        console.timeEnd("Counting");
    });

    createButton("Create Random Grid", function () {
        printGrid(createIncRandomGrid(100));
    });

    createButton("Create Correct Random Grid", function () {
        printGrid(createCorRandomGrid(17));
    });

    createButton("Check Grid", function () {
        checkGrid(retrieveGrid());
    });

    createButton("Count Full Cells", function () {
        console.log(findFullCells(retrieveGrid()).length);
    });

    createButton("Count Empty Cells", function () {
        console.log(findEmptyCells(retrieveGrid()).length);
    });

    createButton("Sort Empty Cells", function () {
        console.log(sortPossibilties(retrieveGrid()));
    });

    createButton("Sort Full Cells", function () {
        console.log(sortFullCells(retrieveGrid()));
    });

    createButton("Reset Grid", function () {
        printGrid(createEmptyGrid());
    });

1 Ответ

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

Я на самом деле не тестировал его, но тестировал аналогичную функцию.

Попробуйте это в конце, заменив последние восемь строк: 

if (countAllSolutions(grid) < 2) grid = removeNrs(grid, nrsToBeRemoved);
else grid[row][column] = value;
return grid;
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...