Basically I am confused as to what "the general problem of solving N×N Sudoku puzzles is NP-complete" really means. Does it mean that if I have an algorithm which takes a NxN Sudoku board as input and solves it the algorithm must be exponential in time complexity with regards to N? Or is "the general problem" finding ALL NxN Sudoku boards which are valid puzzles?
The reason I am asking is because I have an algorithm which solves an NxN Sudoku board in polynomial time, thus I am confused as to what "the general problem of Sudoku" really means.
The algorithm itself is rather simple, treat all the positions on the NxN sudoku board as unknown variables (thus we have N^2 variables), then set up a system of equations for all those variables, write it in matrix form we get a N^2 by 3N matrix with only ones and zeros, representing which positions should be added together for the rows,columns and boxes in the sudoku puzzle. Now we have the sudoku problem on the form Ax = b, where A is our large matrix, x is the vector we want to find and b is a vector with the sum of all values (for example 45 on a 9x9 sudoku board). Instead of representing the values on the sudoku board with numbers (for example 1 to 9) they are represented with a one-hot encoding (so 4 is [0,0,0,1,0,0,0,0,0] etc). Thus x and b in the equation becomes "vectors of vectors" (Note, NOT a matrix, we still treat Ax as if x was scalar, so each element in A scales a whole vector in x, so not matrix multiplication). the b vector becomes the sum of all one-hot encoding vectors, i.e a vector with only ones.
Now we just account for the known values on the sudoku board by setting the elements in the A matrix which correspond to the known board position to zero and subtract the value (one-hot encoding) in the b vector. Then we just use Gauss elimination to solve the system, thus we can still treat the one-hot encodings in the b vector as scalars which are just being added/subtracted and scaled. Once we have completed the gauss elimination we are left with the solution in the b-vector. Since the sudoku is unique we should have just one solution, and because of the one-hot encoding we can also check if a sudoku is valid, since if the b-vector contains anything but 1's and 0's it is not a valid puzzle. The gauss elimination also tells us if there are multiple or no solutions since the last rows will be completely 0 or 0 = 1 for no solutions. Another benefit of the one-hot encoding is that you can easily find the solution when the system is underdetermined. Since you know all x values only have a single one it eliminates many possible solutions. Consider the case where the A matrix has a row of [3,1,2,0,0,0] and the corresponding b-value is [0,0,2,0,3,1]. Then you know that the 3, 2 and 1 all pair up, since it is the only way you can get this result using one-hot encoded values on x. The same principle can be used to quickly solve which x correspond to which b value when you have an underdetermined A matrix with only ones and zeros.
Gauss elimination is cubic in time complexity in regard to the size of the matrix, the size of the matrix is N^2 with regards to the sudoku board size, this the algorithm gets a time complexity of N^6 with regard to the board size.
I have very likely overlooked something or misunderstood the NP-completeness of the general sudoku problem, but that's why I'm asking this question :)
