javascript中的数独求解器回溯

Question

我试图使用回溯在JavaScript中创建一个数独求解器，我做了一些研究，看到了类似的问题，但我的方法不同；而且没用。

var grid = [ // Empty grid to test the solver
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0]
           ];
var invalid = [ // Here go additional invalid numbers
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
               [[],[],[],[],[],[],[],[],[]],
              ];

function sudokuSolver() { // The solver function
    for (var r = 0; r < 9; r++) { // For each row
        for (var c = 0; c < 9; c++) { // For each column
            for (var n = 1; n < 11; n++) { // For each number + 10
                if (n == 10) { // If no solutions were found for the current cell, backtrack.
                    if (c == 0) { // If at left-most position
                        var x = grid[--r][8]; // Assign the number in the previous cell to "x". Decremented "r" because the previous cell is in the previous row, and the number in it should be changed
                        invalid[r+1][0] = []; // Reset invalid numbers for current cell
                        invalid[r][8].push(x); // Mark "x" as invalid in the previous cell
                        c = 7; // The number in the previous cell should be changed, the previous cell is in column 8, the loop increments each time the code block is executed, so c here should hold 8 - 1 = 7
                    } else { // Same goal here
                        var x = grid[r][--c]; 
                        invalid[r][c+1] = [];
                        invalid[r][c].push(x);
                        c--;
                    }
                    break;
                } else if (isValid(r, c, n)) {
                    grid[r][c] = n; // If n is valid, put it
                    console.log(r + ',' + c + ',' + n);
                    break; // And break the loop (it won't reach n = 10)
                }
            }
        }
    }

    // Print the solution
    for (var r = 0; r < 9; r++) {
        for (var c = 0; c < 9; c++) {
            document.getElementById('sudoku').getElementsByTagName('tr')[r].getElementsByTagName('td')[c].innerHTML = grid[r][c];
        }
    }
}

function isValid(r,c,n) {
    var a;
    var b = true;
    var col = '';
    for (var i = 0; i < 9; i++) {
        col += grid[i][c];
    }
    var sec = '';
    for (var lr = 3 * Math.floor(r / 3); lr < 3 * Math.floor(r / 3) + 3; lr++) {
        for (var lc = 3 * Math.floor(c / 3); lc < 3 * Math.floor(c / 3) + 3; lc++) {
            sec += grid[lr][lc];
        }
    }
    a = (grid[r].toString().indexOf(n) == -1 && col.indexOf(n) == -1 && sec.indexOf(n) == -1);
    for (var i = 0; i < invalid[r][c].length; i++) {
        if (n == invalid[r][c][i]) b = false; break;
    }
    return (a && b);
}

使用它，浏览器停止响应，然后询问是否停止脚本。

在控制台中，我得到:1,5,7 1,6,3 1,5,7 1,6,3...

有什么问题的线索吗？

if (n == invalid[r][c][i]) b = false; break;

if (n == invalid[r][c][i]) {b = false; break;}

Answer 1

你有一个无限循环

for (var c = 0; c < 9; c++) {…}

退出循环的唯一方法是使c>=9。通常，当C++最终使其递增时，就会发生这种情况。但是，当n==10时，逻辑将始终执行某种递减(--C、--和C=7)，以防止C达到9。

因此，当引入n==10代码分支时，c的递减对于管理c的for循环的每一次迭代都会发生一次，因为递减是c=7或c=C-2，它不会到达9并结束循环。

答案是不要改变循环内的值。重构代码以管理R、C和N，就好像它们在for循环块中是不可变的一样。然后对块中的这些值执行计算，以找到执行业务逻辑所需的值。也许是制造中间变量来存储中间值。

另一个很大的帮助是将逻辑的每个部分分解成函数。这样做可以帮助您抽象复杂度，这样可以帮助您集中精力，而且由于它们是函数，它们可以是确定性的。意味着您所投入的内容将产生可预测的输出。然后，这只是一个问题，组成的功能，在顺序和希望执行业务逻辑。