使用巨型哈希表在多项式时间内解决数独

假设您要创建一个哈希表,将每个可能的有效9x9数独(尚未填写)映射到其解决方案.(这是不可行的任务)

然后你要创建一个简单的程序,它将一个有效的9x9数据(再次,尚未填充)作为输入,并返回在上述哈希表中映射到它的解决方案.

这不会被认为是在多项式时间内工作的数独求解器吗？

有没有关于这个理论解决方案的东西使它无法证明数独是P类问题？

我认为你误解了这个问题.来自维基百科:

已知在n×2×n ^ 2个n×n块网格上求解数独谜题的一般问题是NP完全的.

虽然游戏最常见的是9x9变体,但一般说明的问题表征了网格大小与寻找解决方案的复杂性之间的关系 - 而不是任何单独的网格.如果您的假设是正确的,那么它不会从根本上改变问题的分类.

另外,考虑如何从这样的哈希表中检索候选解决方案.如果你的钥匙使用所有的初始值和它们的位置的顺序,那么你就需要保持初始值的所有可能的套(81选30,1.4e22) - 每个独特的解决方案(6.7e21).(这只适用于以30个值开头的解决方案......)