代码之家 › 专栏 › 技术社区 › svaerth

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

np sudoku complexity-theory hashtable

4

svaerth · 技术社区 · 8 年前

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

然后创建一个简单的程序,该程序将有效的9x9数独(同样,尚未填写)作为输入,并在上面描述的哈希表中返回映射到它的解决方案。

这难道不是在多项式时间内工作的数独解算器吗?

这个理论解决方案是否有什么地方使它不能证明数独是一个P类问题?

1 回复 | 直到 8 年前

1

9

Max Vu 8 年前

我想你误解了这个问题。从…起 Wikipedia :

在nn块的n^2n^2网格上求解数独难题的一般问题是NP完全问题。

虽然游戏通常是9x9的变体,但通常所说的问题是网格大小与找到解决方案的复杂性之间的关系,而不是任何单个网格。如果你的假设是真的,它不会从根本上改变问题的分类。

此外,请考虑如何从这样的哈希表中检索候选解决方案。如果使用所有初始值的序列及其位置作为键,则需要为每个唯一解决方案(6.7e21)保留所有可能的初始值集(81选择30,1.4e22)。(这仅适用于以30个值开头的解决方案,显示…)