algorithm - 数独算法 X 的时间复杂度是多少？

Question

我在这里找到了一个声明，即数独的算法 X具有 O(N^3) 时间复杂度，其中 N 是棋盘大小。

这可能是合乎逻辑的，因为对于数独，要计算的二进制矩阵有 N^3 行。但这使得数独问题可以在多项式时间内解决，而数独被称为 NP 问题，这意味着（据我所知）

• 不可能总是在多项式时间内求解

• 可以在多项式时间内验证解决方案

那么算法 X 的数独时间复杂度是多少，是否有可能在多项式时间内解决数独问题？

谢谢！

Answer 1

数独数学很好地解释了这一点：

在 n×n 块的 n^2×n^2 网格上解决数独难题的一般问题已知是 NP 完全的。

因此，求解数独的任何算法的运行时复杂度至少是 n 的指数。对于普通的数独 (n = 3)，这意味着 O(N^3) 是完全合理的。

Answer 2

完整的运行时间分析见：https ://11011110.github.io/blog/2008/01/10/analyzing-algorithm-x.html

那里说

即使是最愚蠢的算法 X，它避免任何回溯的机会，并且总是以最大化其运行时间的方式选择它的枢轴，最多需要 O(3 ^{n /3} )

它将算法置于指数运行时间 (EXPTIME)中。