Sudoko求解器的时间复杂度及其与NP-完备性的关系

Question

基本上我搞不懂“解N×N数独难题的一般问题是NP-完全”到底是什么意思。这是否意味着，如果我有一个以NxN数独板为输入并求解的算法，则对于N，该算法的时间复杂度必须是指数级的。还是“一般问题”找到了所有NxN数独板，这些都是有效的谜题？

我之所以问这个问题，是因为我有一个算法，可以在多项式时间内解决一个NxN数独板，所以我对“数独的一般问题”到底是什么意思感到困惑。

该算法本身很简单，将NxN sudoku板上的所有位置作为未知变量(因此我们有N^2变量)，然后为这些变量建立一个方程组，用矩阵的形式写出，我们得到一个只有1和0的N^2×3N矩阵，表示在sudoku拼图中的行、列和框应该加在一起的位置。现在我们有了形式A_x = b上的sudoku问题，其中A是我们的大矩阵，x是我们想要找到的向量，b是所有值之和的向量(例如9x9 sudoku板上的45 )。它们不是用数字(例如1到9)来表示sudoku板上的值，而是用一次热编码表示(so 4为0、0、1 0、0、0、0、0、0、0等)。这样，方程中的x和b就变成了“向量的向量”(注意，不是矩阵，我们仍然把A_x当作标量，所以A中的每个元素都是x中的一个整体向量，所以不是矩阵乘法)。B矢量成为所有热编码向量的和，即只有一个热编码向量的向量。

现在，我们只考虑sudoku板上的已知值，将A矩阵中对应于已知板位置的元素设置为零，并减去b向量中的值(一次热编码)。然后用高斯消去法求解系统，这样我们仍然可以将b矢量中的一次热编码作为标量来处理，这些标量只是加/减和缩放。一旦我们完成高斯消除，我们剩下的解在b-向量中。由于sudoku是唯一的，我们应该只有一个解决方案，而且由于一个热编码，我们也可以检查sudoku是否有效，因为如果b向量包含1和0以外的任何内容，那就不是一个有效的谜题。高斯消除也告诉我们是否有多个或没有解决方案，因为最后一行将是完全0或0=1，因为没有解决方案。一次热编码的另一个好处是，当系统被低估时，您可以很容易地找到解决方案。因为您知道所有的x值只有一个，所以它消除了许多可能的解决方案。假设A矩阵有一行为3,1,2,0,0,0，0，1的行，对应的b值为0,0,2,0, 3，1。那么你就知道3，2和1都是对的，因为这是使用x上一个热编码值就可以得到这个结果的唯一方法。同样的原理可以用来快速求解当你有一个只有1和零的欠确定的A矩阵时，哪个x对应于哪个b值。

对于矩阵的大小，高斯消去的时间复杂度是三次的，对于sudoku板的大小，矩阵的大小是N^2，对于板大小，该算法的时间复杂度为N^6。

我很可能忽略了一些东西，或者误解了NP--一般sudoku问题的完整性，但这就是我问这个问题的原因:)

Answer 1

我在算法中犯了一个错误。我只在小sudoku上尝试过，在小sudoku上，问题降到了2-SAT问题，因此我错误地假设，对于较大的sudoku，它也是2-SAT问题，但是它很快就变成了3-SAT，甚至更大。