sudoku - 数独 np 完整吗？

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

12 个月前关闭。




Improve this question




我确实通过了 this .

我不明白这个。

当推广到 n 时，数独是 NP 完全的
×
但是 n 网格
一个标准的 9
×
9
数独是
不是
NP-
完全的。

Answer 1

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

区别在于算法是否可以假设输入的大小，或者必须等到它收到输入才能查看它有多大。

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

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

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

并非所有输入都具有相同的大小，因为来自有限字母表的固定符号串只能编码有限数量的谜题。一旦输入具有不同的大小，您可以考虑作为输入大小的函数，您的算法必须做多少工作。 (现在仅仅读取输入是一个 O(n) 操作；解决问题所需的工作可能，而且通常更大。)