logo标签列表

JavaScript中的递归回溯算法

javascriptrecursionbacktrackingsudokurecursive-backtracking
3
我目前在学习回溯算法，并且正在制作数独游戏。我理解算法的基本工作原理，并使用它编写了数独求解器。
我的当前问题与从已完成的数独网格中删除一定数量的数字以创建具有唯一解的有效数独相关。
我已经查看了类似的问题，但没有找到答案。
这是一个已解决数独网格的示例：
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之前完成。

非常感谢任何帮助、解释或可阅读的内容。

编辑：

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，函数将“返回false”。我们进入递归的上一级，在这里，“removeNrs（grid，nrsToBeRemoved）”现在是“false”。这意味着尽管当前状态下的网格很好，但该函数会撤消自己的更改并再次返回false。反复执行此操作，直到网格填满为止，函数才以“false”退出。 - user5734311
好的，我明白了。我该如何更改我的代码，使其只回溯一步，然后尝试另一个选项？这就是我未能实现的。 - dthill
1个回答
0

我实际上还没有测试过它，但我测试过一个类似的函数。

在结尾处尝试这个，替换你最后的八行代码：

if (countAllSolutions(grid) < 2) grid = removeNrs(grid, nrsToBeRemoved);
else grid[row][column] = value;
return grid;
这几乎可以工作。如果要删除一小部分数字，则完美运行，但对于较大数量的数字40+，一旦有多个解决方案，它就会放弃并返回最后一个工作网格。这使我从数独中删除了大约35-40个数字。我在您的else子句中添加了'grid = removeNrs（grid，nrsToBeRemoved）'，我通过回溯工作到了约45-50个数字的删除，但由于某种原因它在'nrsToBeRemoved <= 0'之前提前退出。 - dthill
如果你将函数调用添加到else子句中，最终会导致无限递归... 没有访问你所有代码的情况下，我无法真正解决这个问题。也许错误出现在其他地方。 - user5734311
我已经在上面添加了整个代码。它非常长，我更改了一些名称以更好地适应其余的代码。该代码生成一个表格，以便您可以查看结果。非常感谢您的帮助。 - dthill
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接