我在这里发现了一个语句，即数独的算法X具有O（N^3）时间复杂度，其中N是电路板大小。
这可能是合乎逻辑的，因为对于数独，要计算的二进制矩阵有 N^3 行。但是这使得数独问题可以在多项式时间内解决，并且数独已知是NP问题，这意味着（据我所知）
-
不可能总是在多项式时间内求解
-
可以在多项式时间内验证解决方案
那么数独算法X的时间复杂度是多少，是否有可能在多项式时间内解决数独问题？
谢谢！
数独的数学很好地解释了这一点：
在n^2×n^2网格上解决数独谜题的一般问题×n 已知块是NP完全的。
因此，任何求解数独算法的运行时复杂度在 n 中至少是指数级的。对于正常的数独 （n = 3），这意味着 O（N^3） 是完全合理的。
有关运行时间的完整分析，请参阅：https://11011110.github.io/blog/2008/01/10/analyzing-algorithm-x.html
那里说
即使是最愚蠢的算法X版本，避免任何回溯的机会，并且总是以最大化其运行时间的方式选择其枢轴，最多需要O（3n/3）
将算法置于指数运行时间 （EXPTIME） 中。