数独回溯算法

  • Z时代
  • 2024-01-10
  • 分类：问答

首先，我要声明这是大学的工作，所以我并没有要求别人为我编写代码，我只需要指出正确的方向即可。:)

好的，因此我需要编写一种算法来解决任意大小的（可解决的）数独板。我编写了一个递归函数，可以快速（〜1ms）求解任何9x9电路板，但是当我做较大的电路板（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电路板可以解决得很快。

任何想法或建议都绝对很棒。如果有任何我想念的信息，也请告诉我！

回答：

在仅用一种选择填充方块与在板上完全递归之间，您可以执行更多高级操作。让我们以“区域”为一行，一列或一个正方形区域（3x3或4x4）。

回答：

如果某个区域中只能有相同的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。

回答：

如果仅在一个正方形中的区域中出现一个数字，则从逻辑上讲该正方形将保留该数字。

回答：

战术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的特例。

回答：

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

回答：

缓存结果。所有区域都应具有“脏”标志，该标志表示该区域中的某些内容自上次处理该区域以来已发生更改。您无需处理未设置此标志的区域。

人类会使用所有这些策略，并且非常讨厌猜测数字，因为回溯确实是一个痛苦。实际上，董事会的难易程度是用解决董事会所需的最少猜测量来衡量的。对于大多数“极致”板，一个很好的猜测就足够了。

以上是 数独回溯算法 的全部内容， 来源链接： utcz.com/qa/415098.html

回到顶部