我发现here >数独的Algorithm X＞O（n 3）时间复杂度，其中n是板尺寸。
这也许是合乎逻辑的，因为对于数独来说，要计算的二进制矩阵有n^3行。但这使得数独问题可以在多项式时间内求解，而且数独被认为是NP问题，这意味着（据我所知）
不可能总是在多项式时间内求解
可在多项式时间内验证解
那么数独算法X的时间复杂度是多少呢？
有没有可能在多项式时间内解数独呢？
谢谢您！
最佳答案
Mathematics of Sudoku很好地解释了这一点：
n^2×n^2网格上数独解题的一般问题
已知块是np完全的。
求解数独的任何算法的运行时复杂度至少是指数n。对于正常数独（n＝3），这意味着O（n ^ 3）是完全合理的。
关于algorithm - 数独算法X的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54184595/