递归:JS中的回溯数独求解器

Recursion: Backtracking sudoku solver in JS

本文关键字:回溯 JS 递归      更新时间:2023-09-26

我无法让这个递归算法工作。它应该解决一个数独网格(一个由int组成的2d数组)。我在Java中也做了同样的事情(当然是OOP),它运行得很好。但在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);
}

很难找到。。。但问题出在

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

Javascript只使用浮点数,所以这并不是在做你认为正在做的事情。

解决方案是

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

在javascript中,数字不能强制为整数,所以像(a / 3) * 3这样的东西与a没有什么不同。在isBoxOk中,您需要更换

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

通过

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