假设您要创建一个哈希表，将每个可能的有效9x9数独（尚未填写）映射到其解决方案。 （这是一项不可行的任务）
然后，您将创建一个简单程序，以一个有效的9x9数独（同样，尚未填写）作为输入，并返回映射到上述哈希表中的解决方案。
难道这不算是可以在多项式时间内工作的数独求解器吗？
这种理论上的解决方案是否有某些东西使它无法证明数独是P类问题？
最佳答案
我认为您误解了这个问题。从Wikipedia：
已知在n×n个块的n ^ 2×n ^ 2网格上求解数独难题的一般问题是NP完全的。
尽管游戏通常可能是9x9的变体，但通常所说的问题是网格大小与寻找解决方案的复杂性之间关系的特征-并非任何单独的网格。如果您的假设是正确的，则不会从根本上改变问题的分类。
另外，请考虑如何从此类哈希表中检索候选解决方案。如果将所有初始值及其位置的序列用作键，则需要为每个唯一解（6.7e21）保留所有可能的初始值集（81选择30、1.4e22）。 （这仅适用于以三十个值开头的解决方案……）
关于hashtable - 使用巨型哈希表在多项式时间内求解数独，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49620444/