数独游戏是否是 NP 完全问题？

Question

我确实阅读了这个。

我不理解这个。

数独在泛化到 n × n 格子的情况下是 NP 完全问题，然而标准的 9 × 9 数独不是 NP-完全问题。

- Akhil

---

我提议关闭这个问题，因为这是一个计算复杂性问题，更适合在https://cs.stackexchange.com上讨论，而在SO上则不属于主题。 - cigien

Answer 1

正确的，任何一个9x9数独都可以在O（1）时间内解决（一个1x1数独、4x4数独、甚至1000x1000数独也是如此），因为输入大小是固定的。NP完备性是一个概念，适用于具有可变输入大小的决策问题，因此您可以分析算法的运行时间，因为该输入大小按渐近方式增长。

区别在于算法是否可以假定输入的大小，还是必须等到接收到输入后才能看到其大小。

输入不必以二进制编码；它只需要使用一些有限大小的字母表即可。对于固定大小的数独，您可以选择一个字母表，其中每个可能的谜题都有一个唯一的符号。（在实际中，您可以将理论字母表编码为二进制，每个字母表符号都有一个固定大小的二进制字符串。这就是ASCII的工作原理。输入大小仍然是恒定的；只是一个比1大的常数。）然后，算法使用硬编码表格，将输入字母表中的每个符号与其解决方案配对。解决难题的常数时间算法只是表格查找。

现在考虑那些没有固定大小的难题。有无限数量的可能难题，因此算法必须指定一些编码方案，可以使用有限大小的字母表来描述无限数量的难题。这有两个直接后果。

1. 您不能在有限的空间中存储所有可能输入的解决方案，因此一旦看到输入，您的算法需要进行实际工作来解决难题。

2. 并非所有输入都具有相同的大小，因为来自有限字母表的固定符号字符串只能编码有限数量的难题。一旦输入具有不同的大小，您就可以考虑算法需要执行多少工作作为输入大小的函数。（仅读取输入现在是O（n）操作；解决问题所需的工作可能会更多，通常情况下是更多。）

- chepner

---

不可以，因为一个能够解决9x9数独的算法不能解决任意大小为n x n的数独。 - chepner

你必须准确地描述你要解决的问题。解决9x9数独问题与解决“n” x “n”数独问题非常不同。 - chepner

这是完全误导性的。我认为你在滥用计算复杂性的许多概念。数独因其与精确覆盖问题的严格推导结果及其等价于SAT问题而被知道是NP完全问题。9x9确实是NP完全问题，因为你将无法为任何难题提供可行的多项式时间算法，无论你使用多少演绎技巧。 - Brett Hale

不，n x n数独的一般问题是NP完全问题。仅仅因为一个算法运行在常量时间并不意味着它快；它只是意味着它不随输入大小变化，而一个输入大小不能变化的算法从本质上来说是一个常量时间算法。 - chepner

数独可以转化为一个NP完全问题。数独本身可以通过一组简单的技巧来解决，这些技巧可以很容易地编写成一个小型Python程序，并且几乎可以立即解决。这实际上取决于规则，因为9x9对于每个3x3方格都有约束条件，并使用数字1到9。因此，在9x9之外，您需要定义什么是数独。但是，9x9肯定不是NP完全的，几乎所有的问题都可以用一些基本的一阶逻辑来解决，只有少数需要进行单个递归排除搜索。在进行这样的转换之前，需要明确定义概括。 - Gregory Morse

Answer 2

当N趋向于无穷大时，您正在分析一个复杂度为O(N)的问题。但是，您输入的问题不会随着N趋近于无穷而变化，您有一个有限的上限。这个上限是恒定的。

原因是有一个有限的解集。您可以列出每一个9x9数独并进行枚举。将所有解都编入一个字典，并以已知输入值作为索引。找到一个解就只需要在您预生成的字典中进行常量时间查找。重要的是这个列表是巨大的，但它是有限的。

实际上，另一种解决方案是生成所有可能的数独网格，直到找到一个解决您的输入的解。这可能看起来像是一个线性的解决方案，但由于存在一个有限的上限，实际上是一个常数时间算法。

- Emil Vikström