我有一个项目要完成复杂性和解决问题的课程，我决定将项目建立在数独上。根据我所做的研究，数独是一个 NP-Complete 问题（这是项目所必需的），我找到了一些为其创建算法的方法。我打算做一个蛮力解决方法，我需要做另外两种方法。我找到了一些方法，例如将其解决为精确覆盖问题，并且我找到了一篇将数独描述为 SAT 问题的论文。但我的问题是：数独是否有经过验证的多项式解决方案？我的老师似乎认为大约 5 年前一位“高级”绅士有一个“聪明”的解决方案，但他只记得这些。有谁知道这个解决方案是什么，或者任何其他多项式解决方案是什么？我'
谢谢！
因为广义数独问题（n 2 × n 2网格）是 NP 难的，如果有一个已知的多项式时间算法来解决数独难题，它将证明 P = NP。那将是一笔大买卖。
需要记住的是，我们所知道的数独游戏都是 9 × 9 的网格。因此，当试图测量解决数独难题的时间复杂度时，使用大 O 表示法实际上并不是一个好主意，因为大 O 表示法讨论的是算法在长期内如何扩展以及我们所关心的about 是解决固定大小的数独谜题。换一种说法，如果您想谈论解决数独难题的多项式时间，您必须回答“什么变量中的多项式？ ”如果您一直在解决 9 × 9 数独网格，那么答案问题不是很清楚。
您也可以使用类似人类的策略，它可以是多项式，但它不会为所有数独找到解决方案（即使是具有唯一解决方案的数独）。将数独简化为图形着色问题也很容易（每个单元格由图形的一个节点表示，节点根据数独规则连接，以免具有相同的颜色。预填充节点接地到一些颜色）。