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()是否返回true。我认为我的问题来自于 possible () 函数中的 double for ，它从整个数组开始，但我不知道如何让它停止在这种情况下......

Answer 1

我认为我的问题来自于 possible () 函数中的 double for

这对我来说看起来不错。双 for 循环可能非常慢，但在这种情况下，每个循环仅进行 3 次迭代，因此内部主体仅执行 9 次。这没什么大不了的。

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

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

Answer 2

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

目前的方法：

• 你正在检查每一个未填充的空间。第一次迭代中大约 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 选项转移到更合理的选项。 这将导致更快失败，进而意味着需要覆盖的选项更少。

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

• 更新字段时，只需从[行、列、方]中删除新值即可。

• 检查字段的可用性时，检查该字段是否适用于每个[行、列、方块]

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