Problem Detail: 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?
Asked By : user2566092
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47249
