递归：JS回溯数独求解器

Question

我无法让这个递归算法起作用。它应该解决数独格子（一个由整数组成的二维数组）。我已经用Java做了同样的事情（当然是面向对象的），而且它运行得很好。但在JS中却不行。网格中的值没有被改变，而且它从未达到基本情况。该算法是solveSudoku-基本情况是当它遍历整个网格但没有找到任何“空”单元格（值为'0'）时。

我把所有的代码都放在一个文件中。你能找出错误吗？我已经试了一个星期了，快要放弃这个小项目了。

"use strict";

var grid = [
        [0,0,8,4,0,3,5,0,6],
        [0,0,3,1,0,2,0,0,4],
        [0,4,5,7,0,0,0,9,0],
        [6,9,0,0,0,5,0,0,7],
        [0,8,0,0,0,0,0,5,0],
        [4,0,0,3,0,0,0,1,8],
        [0,7,0,0,0,6,2,4,0],
        [1,0,0,5,0,7,8,0,0],
        [8,0,6,9,0,1,3,0,0]
    ];

// recursive algo
function solveSudoku(grid, row, col) {
    var cell = findUnassignedLocation(grid, row, col);
    row = cell[0];
    col = cell[1];

    // base case: if no empty cell  
    if (row == -1) {
        console.log("solved");
        return true;
    }

    for (var num = 1; num <= 9; num++) {

        if ( noConflicts(grid, row, col, num) ) {   
            grid[row][col] = num;

            if ( solveSudoku(grid, row, col) ) {                
                return true;
            }

                    // mark cell as empty (with 0)    
            grid[row][col] = 0;
        }
    }

    // trigger back tracking
    return false;
}


function findUnassignedLocation(grid, row, col) {
    var done = false;
    var res = [-1, -1];

    while (!done) {
        if (row == 9) {
            done = true;
        }
        else {
            if (grid[row][col] == 0) {
                res[0] = row;
                res[1] = col;
                done = true;
            }
            else {
                if (col < 8) {
                    col++;
                }
                else {
                    row++;
                    col = 0;
                }
            }
        }
    }

    return res;
}

function noConflicts(grid, row, col, num) {
    return isRowOk(grid, row, num) && isColOk(grid, col, num) && isBoxOk(grid, row, col, num);
}

function isRowOk(grid, row, num) {
    for (var col = 0; col < 9; col++)
        if (grid[row][col] == num)
            return false;

    return true;
}
function isColOk(grid, col, num) {
    for (var row = 0; row < 9; row++)
    if (grid[row][col] == num)
        return false;

    return true;    
}
function isBoxOk(grid, row, col, num) {
    row = (row / 3) * 3;
    col = (col / 3) * 3;

    for (var r = 0; r < 3; r++)
        for (var c = 0; c < 3; c++)
            if (grid[row + r][col + c] == num)
                return false;

    return true;
}

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);
}

- olefrank

---

你在控制台中收到任何错误消息吗？ - Niet the Dark Absol

没有错误信息。它只是打印出未更改的网格。我正在使用Chrome和FireFox。 - olefrank

代码看起来没问题。我只能假设这意味着你特定的数独难题不能朴素地解决。 - Niet the Dark Absol

Java可以！JS递归能力是否存在某些限制，例如对堆栈的调用次数过于有限等。 - olefrank

代码几乎没问题，这个谜题确实可以用它来解决 :-) - 6502

除了其他人说的方法之外，本地变量“grid”正在遮盖全局变量“grid”。我会将全局变量重命名为“gGrid”。 - Yetti99

Answer 1

找到它有点棘手……但问题出在

row = (row / 3) * 3;
col = (col / 3) * 3;

Javascript使用的是浮点数，因此这并不是您认为的那样。

解决方案是：

row = Math.floor(row / 3) * 3;
col = Math.floor(col / 3) * 3;

- 6502

---

啊！太棒了！不太确定我是怎么错过了它，因为这对浮点数来说有点像 no-op XD - Niet the Dark Absol

Answer 2

在JavaScript中，数字无法被强制转换为整数，因此类似于 (a / 3) * 3 的表达式与 a 并无区别。 在isBoxOk函数中，您需要进行替换。

row = (row / 3) * 3;
col = (col / 3) * 3;

by

row = Math.floor(row / 3) * 3;
col = Math.floor(col / 3) * 3;

此外，我认为您可以简化findUnassignedLocation函数：

function findUnassignedLocation(grid, row, col) {
    for (; row < 9 ; col = 0, row++)
        for (; col < 9 ; col++)
            if (grid[row][col] == 0)
                return [row, col];
    return [-1, -1];
}

- Lithy