简单回溯暴力算法最坏情况下有效的数独谜题是什么？

Question

数独的“简单/朴素回溯强力算法”、“直接深度优先搜索”是众所周知并已实现的。

并且似乎不存在不同的实现。（当我第一次写这个问题时..我想说我们可以完全标准化它，但措辞很糟糕..）

我认为这个人很好地描述了该算法：/sf/answers/145284891/

编辑：所以让我用伪代码更详细地说明它......

var field[9][9]
set the givens in 'field'
if brute (first empty grid) = true then
    output solution
else
    output no solution
end if

function brute (cx, cy)
    for n = 1 to 9
        if (n doesn't present in row cy) and (n doesn't present in column cx) and (n doesn't present in block (cx div 3, cy div 3)) then
            let field[cx][cy] = n
            if (cx, cy) this is the last empty grid then
                return true
            elseif brute (next empty grid) = true then
                return true
            end if
            let field[cx][cy] = empty
        end if
    next n
end function

我想找到最需要时间的谜题。对于这种特定的“标准化”算法，我们可以称其为“最难”，但这并不像那些要求“最难的数独”的问题。

事实上，只要简单地旋转或翻转，这个定义下的“困难”谜题就可能变得超级简单。

根据“对于每个网格尝试数字1到9”的规则，它从1开始尝试，所以我们可以以某种方式让它通过使用适当的数字尝试更多，这样就不会出现排列问题。

数独谜题必须有效，即它应该恰好有 1 个解决方案。有人得到了一个需要 1439 秒的谜题，但由于没有答案而无效。

我定义所需的时间（或者说时间复杂度）相当于输入递归函数的次数。（在我的实现中，它与上面的伪代码略有不同，因为最后一个入口，并确保唯一的解决方案等）

有没有什么好的方法来构造它，或者我们必须使用启发式算法等近似方法来找到不精确的解决方案？

---

我已经使用朴素策略（我在上面称为“简单”，它是唯一的）和 Peter Norvig 的“最少候选者优先”策略（我的实现是确定性的，但不是唯一的。正如 Peter 也提到的那样）实现了回溯。 python dict 的顺序会极大地改变结果，以防候选人数量平局）。

https://github.com/farteryhr/labs/blob/master/sudoku.c

无解方案一：

.....5.8....6.1.43.........1.5.........1.6...3.......553..... 61.........4.........

在我的笔记本电脑上花了 60 秒才得出无解结论，输入递归函数 2549798781 次（后面称为“循环”）。通过我的 LCF 实现，78308087 个循环在 30 秒内结束。这是因为寻找候选数最少的网格需要更多的操作，LCF策略的单个周期使用大约16倍的时间。

最难列表中最上面的一个：

4.....8.5.3......7......2......6.....8.4......1...... ...6.3.7.5..2.....1.4......

耗时3.0s，在第9727397个周期找到解，第142738236个周期确保解唯一。（我的 LCF：0.004 秒内为 981/7216）

“困难”列表中的许多仍然很容易天真，尽管其中很大一部分需要 10^7 到 10^9 周期。

维基百科：数独求解算法（原始）指出，可以通过在开头制作尽可能多的空网格和顶行 987654321 的排列来构造此类针对回溯算法的谜题。

好在测试..

......3.85..1.2......5.7.....4...1...9.......5.. ....73..2.1........4...9

需要1.4s，69175317个周期寻找解决方案，69207227个周期确保唯一解决方案。不如Peter提供的难点，但是还好，找到解决方案之后就差不多了，搜索结束了。这可能就是第一行按字典顺序变大的方式。（我的 LCF：0.023 秒内为 29206/46160）

是的，这些很明显，我只是要求更好的方法......

---

还有其他方法来衡量数独的难度（通过求解）

---

数独分析师将陷入Peter给出的多解难题（天真419195/419256，LCF 2529478/2529482，是的，有一些难题使LCF做得更糟）：

.....6..59.....82....8..45.........3.........6..3.54.. .325..6.................

这对于朴素回溯 (10008/76703) 和 LCF 回溯 (313/1144) 来说都很容易，但也会让 Sudoku Analyst 陷入困境。

..53.....8......2..7..1.5..4....53...1..7...6..32...8.. 6.5....9..4..3......97..

---

另一个更新：

最困难的数独谜题可通过简单的深度优先搜索算法快速解决

哈，终于有人也在找了，而且还给了一个超难的！以下有效谜题：

9..8......5......2..1...3.1.....6..4...... 7.7.86..3.1..4..2..

本文将该算法命名为SDFS，Straightforward Depth-First Search。作者所说的周期数是1553023932/1884424814，而我的实现是1305263522/1584688020。是的，在弹出计数器的确切位置上会有一些差异，但基本行为是一致的。在 repl.it 的服务器上，找到答案花了 97 秒，完成搜索花了 119 秒。

Answer 1

您可以通过记录所花费的时间/次数轻松生成最坏的情况。您的代码为解决困难的数独难题而执行的操作。您可以使用随机生成器来生成有效的数独谜题（或者）您可以从互联网上获取困难的数独谜题并对其运行代码以测量操作的时间/数量。一旦针对 10000 个此类情况运行代码，最慢的 5 个（以及未解决的）将是您的解决方案的最差情况。

在farter的评论后编辑

我意识到你想提高算法的效率。考虑到 CPU 能力相当高，一个 su-do-ku 谜题需要 97 秒！您可以减少时间

1. 不要使用回溯，仅填写您知道解决方案的方格。编写一个贪心算法，为您永远不会改变的方块找到答案。
2. 并行化您的搜索（同时查找多个方块的解决方案）
3. 你的搜索应该涉及多种贪婪的方法......对于。例如。选择显示最多数字的线条/3x3 正方形/3x9/9x3 矩形，您更有可能显示该区域中的数字，这将减少整个拼图的运行时间。还可以找到特定区域中每个数字的频率，这将有助于快速查找数字。例如，如果在 3x9 正方形中显示出两个 3，则您更有可能显示第三个 3，因为该区域中的第三个 3 应该位于 3 个单元格之一中。
4. 对于困难的谜题，添加记忆......例如。在某些情况下，您知道某一对号码适合一对单元格。但你不知道哪个细胞进入哪个细胞。在这种情况下，您可以确定其他 7 个数字不会出现在这些单元格中。记住这个否定标准并利用它来最大限度地减少搜索时间。

让我知道这是否有帮助。