正确的,任何一个9x9数独都可以在O(1)时间内解决(一个1x1数独、4x4数独、甚至1000x1000数独也是如此),因为输入大小是固定的。NP完备性是一个概念,适用于具有可变输入大小的决策问题,因此您可以分析算法的运行时间,因为该输入大小按渐近方式增长。区别在于算法是否可以假定输入的大小,还是必须等到接收到输入后才能看到其大小。输入不必以二进制编码;它只需要使用一些有限大小的字母表即可。对于固定大小的数独,您可以选择一个字母表,其中每个可能的谜题都有一个唯一的符号。(在实际中,您可以将理论字母表编码为二进制,每个字母表符号都有一个固定大小的二进制字符串。这就是ASCII的工作原理。输入大小仍然是恒定的;只是一个比1大的常数。)然后,算法使用硬编码表格,将输入字母表中的每个符号与其解决方案配对。解决难题的常数时间算法只是表格查找。现在考虑那些没有固定大小的难题。有无限数量的可能难题,因此算法必须指定一些编码方案,可以使用有限大小的字母表来描述无限数量的难题。这有两个直接后果。 您不能在有限的空间中存储所有可能输入的解决方案,因此一旦看到输入,您的算法需要进行实际工作来解决难题。 并非所有输入都具有相同的大小,因为来自有限字母表的固定符号字符串只能编码有限数量的难题。一旦输入具有不同的大小,您就可以考虑算法需要执行多少工作作为输入大小的函数。(仅读取输入现在是O(n)操作;解决问题所需的工作可能会更多,通常情况下是更多。)
当N趋向于无穷大时,您正在分析一个复杂度为O(N)的问题。但是,您输入的问题不会随着N趋近于无穷而变化,您有一个有限的上限。这个上限是恒定的。原因是有一个有限的解集。您可以列出每一个9x9数独并进行枚举。将所有解都编入一个字典,并以已知输入值作为索引。找到一个解就只需要在您预生成的字典中进行常量时间查找。重要的是这个列表是巨大的,但它是有限的。实际上,另一种解决方案是生成所有可能的数独网格,直到找到一个解决您的输入的解。这可能看起来像是一个线性的解决方案,但由于存在一个有限的上限,实际上是一个常数时间算法。