Javascript

Question

我想创建一个数独求解器，但我注意到专家级数独需要几秒钟才能显示结果... 这是我的一段代码：

function possible(board, y, x, n) {
    for (let i = 0; i < 9; i++) {
        if (board[y][i] === n || board[i][x] === n) {
            return false;
        }
    }
    const xSquare = Math.floor(x / 3) * 3;
    const ySquare = Math.floor(y / 3) * 3;

    for (let j = 0; j < 3; j++) {
        for (let i = 0; i < 3; i++) {
            if (board[ySquare + i][xSquare + j] === n) {
                return false;
            }
        }
    }
    return true;
}

function solve(board) {
    for (let y = 0; y < 9; y++) {
        for (let x = 0; x < 9; x++) {
            if (board[y][x] === 0) {
                for (let n = 1; n <= 9; n++) {
                    if (possible(board, y, x, n)) {
                        board[y][x] = n;
                        if (solve(board)) {
                            return board;
                        }
                    }
                }
                board[y][x] = 0;
                return false;
            }
        }
    }
    return board;
}

我的函数possible()是看x轴和y轴的数是否不一样，正方形（3x3）是否和当前方框的数不一样

我的函数 solver() 函数用于查看我的数组中是否没有更多的 0 以及可能的函数 possible() me return true.

我认为我的问题来自于 possible () 函数中的 double for，它从整个数组开始，但我不知道如何让它在 case 处停止...

Answer 1

I think my problem comes from the double for in the possible () function

我觉得不错。双 for 循环可能真的很慢，但在这种情况下，每个循环只进行 3 次迭代，所以内部循环体只执行了 9 次。没什么大不了的。

虽然有更快的方法来实现“可能性检查”。例如，通过跟踪在每一行、每一列和每一块中使用了哪些值。如果将其存储为位掩码，则很容易计算（只需几个位数学运算）给定单元格的哪些值是可能的：根本没有循环。

您可以用来加速求解器的主要技术是添加迭代约束传播：迭代查找无需搜索即可直接填充的单元格，例如 Naked Singles and Hidden Singles。根据我的经验，传播是慢解算器和快解算器之间最大的区别，但当然高效的实现也很重要。

Answer 2

目前您正在递归地暴力破解所有可能的组合。我没有任何绕过暴力破解的神奇解决方案。然而，我们可以让蛮力更聪明。

当前方法：

您将检查所有未填写的 space。第一次迭代大约 70-75，随后的每次迭代中减少一个。
对于每个这样的字段，您尝试用每个可能的数字填充它（最多 9 个选项，通常更少）
然后你在一个少填字段的板上递归调用自己
直到您偶然发现第一个可能的解决方案。

您当前正在执行的操作数介于 9^（开始时填充的 81 个位置）（上限，意味着在不修剪的情况下暴力破解每个选项）到更低的数量 - 例如您填充的值越多，您失败并修剪可能性树的分支的频率就越高。实际计数将类似于：7 * 7 * 7 * ... * 6 * 6 * ... * ... 直到完成。

所以第一个可能的改进是更智能的修剪。当且仅当：

它的所有字段都已填写
所有未填写的字段都有超过零个可能的选项。

目前您只勾选了待填字段，也就是说您可以创建稍后会立即被拒绝的董事会。这会创建很多不必要的分支。一些伪代码来说明：

 function possibleCount(board, x, y) {
     /*code to compute available options - e.g. number 0-9*/
     return count
}

function boardPossible(board,x, y, n) {
   board[x][y] = n
   foreach (field in board) {
       if (possibleCount(field) == 0) {
          //if there is any field that is invalidated by inserting
          //the value, we are stuck and we can prune the branch.
          return false 
       }
   }
}

这似乎需要大量额外的计算，但我们在这里进行了权衡。我们将在每一步（计算可能的棋盘选项）上花费更多的时间来尽早修剪大部分分支。
此外，您可以将计算从最初的 7 * 7 * 7 ... * 6 * 6 个选项转移到更合理的值，方法是 首先填写选项最少的字段 .
这将导致更快失败，这反过来意味着要覆盖的选项更少。

我想到的最后一点优化是，每个字段的可用选项的计数可以通过为每一行、每一列和每一个方块提供一个可用选项列表来加快。

更新字段时，只需从[行、列、方块]中删除新值即可。
检查字段的可用性时，检查它是否可用于每个[行、列、方块]

这将消除上述电路板检查引入的大部分开销。不幸的是我目前在工作，但如果我有时间，我稍后会尝试做一些基准测试。

Javascript - 如何优化我的数独游戏？

Javascript - How can I optimize my sudoku?

algorithm

optimization

solver

sudoku