问数独np-完全吗？

EN

正确；任何9x9 Sudoku都可以在O(1)时间内求解( 1x1 Sudoko，或4x4 Sudoko，甚至1000x1000 Sudoku)，因为输入大小是固定的。NP-完备是一个适用于具有可变输入大小的决策问题的概念，因此当输入大小逐渐增大时，您可以分析算法的运行时间。

区别在于算法是否能够假定输入的大小，还是必须等到接收到输入时才能看到它有多大。

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

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

1. 您不能将所有可能的输入的解决方案存储在有限的空间中，因此您的算法需要做实际的工作来解决一个一旦看到输入的难题。
2. 并不是所有输入都有相同的大小，因为有限字母表中固定的符号串只能编码有限数量的谜题。一旦输入有不同的大小，您就可以考虑算法作为输入大小的函数要做多少工作。(仅仅读取输入现在是O(n)操作；解决问题所需的工作可能而且通常更大。)

当N走向无穷大时，您正在分析O(N)中的一个问题。但是输入问题不随N到无穷大而变化，你有一个有限的上界。这个上限是不变的。

其原因是有有限的一组解决方案。您可以列出并枚举每一个9x9 sudoku。将所有解决方案索引到字典中，以已知的输入值作为索引。然后，在预先生成的字典中找到解决方案只是一个固定时间的查找。清单庞大并不重要，只是它是有限的。

事实上，另一个解决方案是生成所有可能的sudoku网格，直到您找到一个解决您的输入的网格。乍一看，这似乎是一个线性解，但由于有一个有限的上限，它实际上是一个常数时间算法。