javascript - 需要帮助生成数独板的回溯算法

标签 javascript algorithm sudoku

我已经编写了一个生成数独板的算法,但它失败了。我是根据this写的尽管它确实有所不同,因为在我偶然发现这个之前我已经编写了很多代码。

代码

我设置了一个多维数组来保存名为 matrix 的值。 matrix 由 9 个数组组成,每个数组包含 9 列。所以要获得第 4 行第 7 列的值,我会使用

matrix[3][6];

求解所有正方形的函数:

var populateMatrix = function() {
    var possibles = generatePossibleNumbersArray();
    var found = false;
    for(var i=0; i< matrix.length; i++) {
        for(var j=0; j< matrix[i].length; j++) {
            while(possibles[i][j].length > 0) {
                var rnd = Math.floor(Math.random() * possibles[i][j].length);
                var num = possibles[i][j].splice(rnd, 1)[0];
                if(isValid(i, j, num)) {
                    matrix[i][j] = num;
                    found = true;
                    break;
                } else {
                    found = false;
                    continue;
                }
            }
            if(!found) {
                possibles[i][j] = [1,2,3,4,5,6,7,8,9];
                j -= 2;
            }
        }
    }
}   

generatePossibleNumbersArray() 只是一个辅助函数,用于创建与 matrix 完全相同的多维数组,除了它被初始化为每个单元格保存一个整数数组 1-9 .在 populateMatrix() 函数中,这些可能的数字会针对每个单元格进行缩减。

问题

每次都在完成矩阵之前失败,因为 j 最终为 -1。这是因为随着越来越多的单元格被解决,算法越来越难以找到单元格的值,因此它会回溯。但它最终会一直回溯到 j == -1

我真的认为这个算法会起作用,我花了一整天的时间试图解决这个问题,但我很困惑,所以任何人都可以对此有所了解,我们将不胜感激。

我想‘我知道了,我会写一个 javascript 函数来解决数独问题。它能有多难?'。我错了。


[解决方案]

根据@Steve314 的评论(他现在已删除!)我将 matrix[i][j] = undefined 添加到 if(!found) { ... 并且该算法现在可以运行并且速度很快。

如果有人感兴趣,这里是complete code .

最佳答案

如果分支失败,回溯算法通常会恢复状态并执行下一个可能的移动。因此,如果一个字段的随机填充创建了一个失败的分支,只需写回原来的内容即可。

关于javascript - 需要帮助生成数独板的回溯算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6809197/

相关文章:

c# - C#/.NET 在不同场景下的最佳排序算法

algorithm - 数独求解器 Scilab

c - 中止陷阱错误 : 6 - where is it coming from? - 数独求解器

java - 这段代码在保持顺序的同时打印句子的反面有什么问题?

c - 从数组中检索和存储元素(根据条件)

javascript - jquery遍历html元素获取IMG标签

javascript - 如何解决选择国家时动态显示状态的问题?

javascript - Node 无法运行编译 TypeScript

javascript - IE11 不想关注 `disabled` 元素

algorithm - 找到满足给定 f 的属性的最大 f 在其参数中是非递减的