数独回溯算法

在仅用一种选择填充方块与在板上完全递归之间，您可以执行更多高级 *** 作。让我们以“区域”为一行，一列或一个正方形区域（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的特例。

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

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

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