How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?

Question

So usually Sudoku is $9 \times 9$, but this question extends to $n^2 \times n^2$ puzzles with $n > 3$ as well. There are many polynomial time deduction rules that can make progress in finding a solution to a Sudoku puzzle. But then sometimes guessing values and following chains of conclusions might be required to eliminate a cell's value or a combination of cells' values. However, once a valid solution is found, this doesn't guarantee that the solution is UNIQUE. A valid Sudoku puzzle should have only one valid solution but when generating random puzzles, this may take extra computation to verify.

So, my question is, if we allow a certain set of polynomial time deduction rules (say, the most common set described in Sudoku strategy), along with guessing values and following the conclusions, then how much harder can it be to determine there is a unique solution to a given puzzle, versus finding just one solution, in terms of the number of non-unique solutions? Is there an asymptotic difference for certain classes of puzzles?

Answer 1

Yato and Seta show that for every constant $m$, given $m$ solutions to a Sudoku puzzle, it is NP-complete to determine whether there is another solution. They show that the same property is satisfied by other puzzles as well.

Answer 2

If I understand you correctly, you are trying to check Sudoku puzzles that your software have generated to see if they are valid.

If only being “valid” is of interest then Yuval Filmus has already pointed you to a proof that it is NP complete.

However if the aim to find new Sudoku puzzles that a person will enjoy solving, the problem is not as hard. (Having to guess lots of values, due to the puzzle not being solvable using “logic” is no fun!) Therefore personally I would limit the number of guesses to at most 4 and reject any puzzle that can’t be proved to have an unique solution within the limitation of what you consider is reasonable.

Doing the above, using standard back tracking to visit all possible guesses (within your limit), and showing that there is only one solution is much easier then NP complete.

Additionally you can score how hard a puzzle is based on the complexity of the deduction rules it needs and the number of guesses that were needed.

Answer 3

In order to prove that a puzzle is unique, any cell in which a guess had to be made must be branched over. When doing a search to simply find an answer, this is generally done with backtracking, where the solution is the first path in the decision tree which leads to a complete board. In order to prove uniqueness, you must show that only one path leads to a valid solution. This is where things get very difficult to define in terms of run time. The complexity is extremely tied to the actual problem at hand. If you are looking at pure worst case scenario, which is extremely unlikely to occur, then they can be considered the same complexity.

In the worst case scenario, when doing the solve, the solution is within the final possible branch of the tree which can be searched. The entire tree had to be searched to find it, while a search for uniqueness would also require the same search, going over the exact same paths.

Realistically however this is not the case, and with almost all cases involving searching for combinatorial designs, searching for one solution is always faster than searching for all solutions.

In general both of these problems are firmly entrenched in exponential run-times, if not worse.