algorithm - 数独多项式算法？

Question

我有一个关于复杂性和问题解决类(class)的项目，我决定将该项目基于数独。根据我所做的研究，数独是一个 NP-Complete 问题(这是该项目所必需的)，我已经找到了几种为其创建算法的方法。我打算做一个蛮力解决方法，我需要做另外两种方法。我找到了一些方法，例如将其作为 Exact Cover 问题来解决，并且我找到了一篇将数独描述为 SAT 问题的论文。但我的问题是:数独是否有经过验证的多项式解决方案？我的老师似乎认为大约 5 年前有一位“高级”先生提出了一个“聪明”的解决方案，但他只记得这些。有谁知道这个解是什么，或者其他多项式解是什么？如果有任何信息或提示，我将不胜感激。

谢谢!

Answer 1

因为广义数独问题(具有 n² × n² 网格)是 NP-hard，如果存在解决数独谜题的已知多项式时间算法，它将证明 P = NP。那将是一笔巨大的交易。

需要记住的一点是，我们所知道的数独游戏都是 9 × 9 网格。因此，在尝试衡量解决数独游戏的时间复杂度时，使用大 O 表示法实际上并不是一个好主意，因为大 O 表示法讨论的是算法如何长期 而我们所关心的只是解决固定大小的数独谜题。换句话说，如果你想谈论解决数独谜题的多项式时间，你必须回答“多项式在什么变量中？”这个问题，如果你总是解决 9 × 9数独网格，这个问题的答案并不是很清楚。