数独回溯算法

Question

首先,我将说明这是一项大学任务,所以我不是要求别人为我编写代码,我只需要指向正确的方向.:)

好的,所以我需要编写一个算法来解决任意大小的任何(可解决的)数独板.我已经编写了一个递归功能,可以快速解决任何9x9电路板(约1ms),但是当我做大型电路板(16x16)很难解决时,它会挣扎......我已经进行了一次20分钟的测试,它可以'似乎解决了它.它可以解决简单的16x16谜题甚至是一个空白的16x16板,所以我不认为这是问题的维度..它更可能是我认为的问题算法.

无论如何,这是我的程序的基本逻辑..

• 我有一个3D矢量,存储我每个方格的可能值
• 当一个值放在一个正方形中时,它将从它所在的周围正方形,行和列的可能值中删除

然后我的解决功能基本上是:

bool solve() {

    if (there are no unfilled squares)
        return true

    if (the board is unsolvable - there are empty squares that have no possible values)
        return false

    while (there are empty squares)
    {
        int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square

        if (squaresFilled == 0)
            break;
    }

    //exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess

    while (there are empty squares that have choices left) {

        find the square with the least number of choices

        if (the square with the least number of choices has 0 choices)
            return false; //not solvable.

        remove that choice from the 3D vector (vector that has the choices for each square)
        make a copy of the board and the 3D choices vector

        fill the square with the choice

        if (solve())
            return true; //we're done

        restore the board and choices vector 
        //the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.

    }

    return false; //can't go any further
}

这有什么低效的吗？有什么方法可以让它更好地工作吗？我猜测16x16电路板需要这么长时间,因为它的决策树对于没有充分填充的电路板而言是如此之大.但这很奇怪,因为9x9电路板的解决速度非常快.

任何想法或建议都绝对令人敬畏.如果有任何我错过的信息也让我知道!

Answer 1

用于解决数独的快速算法是Donald Knuth的算法X. 你表示解决数独作为精确覆盖问题,然后使用算法X来解决EC问题.然后使用DLX作为算法X的有效实现.

维基百科有很好的解释如何应用精确的封面来解决数独.

我可以告诉你,DLX是一个非常快速的解决数独的解决方案,通常用于最快的algorhitm.

http://www.setbb.com/phpbb/index.php?mforum=sudoku是伟大的论坛,可能是最好的数独程序员.

Answer 2

在仅用一种选择填充方格和在棋盘上完全递归之间，您可以执行更高级的操作。假设“区域”是一行、一列或一个正方形区域（3x3 或 4x4）。

战术1

如果一个区域中有 K 个方格只能取相同的 K 个数字（例如两个方格只能取 2 和 5，或者三个方格只能取 1、7 和 8），那么该区域中的所有其他方格都可以不要接受那些具体的数字。您需要迭代每个区域以清除“已采用”的数字，这样您就可以找到一个只有一个逻辑选择的方格（例如，具有 2、4 和 5 的第三个方格逻辑上只能采用 4，或者具有 1、3、 7和8逻辑上只能取3)。

如果考虑以下示例，则必须通过迭代来解决此问题。一个区域有包含以下可能数字的正方形：

A: 1 2 3
B: 2 3
C: 2 3 4 5
D: 4 5
E: 4 5

该算法应检测到方格 D 和 E 包含数字 4 和 5，因此 4 和 5 被排除在该区域的其他方格之外。然后，算法检测到方格 B 和 C 包含数字 2 和 3，因此将它们从其他方格中排除。这使得方格 A 只剩下数字 1。

战术2

如果一个数字只出现在一个方格的区域中，那么从逻辑上讲，该方格就保存着该数字。

战术3

策略 1 和 2 只是策略 3 的特例，其中 K 个方格只有 K 个相同的数字。您可以拥有 K 个正方形和一组 K 个数字，并且这些 K 个正方形可以容纳这些 K 个数字的任何子集。考虑以下区域示例：

A: 1 2
B: 2 3
C: 1 3
D: 1 2 3 4

方格 A、B 和 C 只能容纳数字 1、2 和 3。这就是 K 代表 K。这意味着任何其他方格在逻辑上都不能容纳这些数字，这使得方格 D 中只剩下数字 4。

当 K = N - 1 时，策略 2 是策略 3 的特例。

战术4

利用区域重叠。假设某个数字只能存在于该区域的某些方格中。如果所有这些方块都属于另一个重叠区域，那么该数字应该从该其他区域中的所有其他方块中排除。

战术5

缓存结果。所有区域都应该有一个“脏”标志，表示该区域中的某些内容自上次处理该区域以来已发生变化。您不必处理未设置此标志的区域。

人类使用所有这些策略，并且真的讨厌猜测数字，因为回溯真的很痛苦。实际上，棋盘的难度是用解决该棋盘所需的最少猜测次数来衡量的。对于大多数“极端”主板来说，一个好的猜测就足够了。