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) {&nbsp; &nbsp; &nbsp;/*code to compute available options - e.g. number 0-9*/&nbsp; &nbsp; &nbsp;return count}function boardPossible(board,x, y, n) {&nbsp; &nbsp;board[x][y] = n&nbsp; &nbsp;foreach (field in board) {&nbsp; &nbsp; &nbsp; &nbsp;if (possibleCount(field) == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //if there is any field that is invalidated by inserting&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //the value, we are stuck and we can prune the branch.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp;}}这看起来需要大量额外的计算，但是我们在这里做出了权衡。我们将在每一步上花费更多的时间（计算可能的板选项）来尽早修剪大部分分支。此外，您可以通过简单地先填充选项最少的字段，将计算从最初的 7 * 7 * 7 ... * 6 * 6 选项转移到更合理的选项。&nbsp;这将导致更快失败，进而意味着需要覆盖的选项更少。我想到的最后一点优化是，通过为每行、列和方块提供可用选项列表，可以加快每个字段的可用选项的计数。更新字段时，只需从[行、列、方]中删除新值即可。检查字段的可用性时，检查该字段是否适用于每个[行、列、方块]这将消除上述电路板检查带来的大部分开销。不幸的是我目前正在工作，但如果我有时间，我稍后会尝试做一些基准测试。