How to show a sodoku solution is unique

Question

Given a unsolved sodoku, how can one show that it has a unique solution?

Answer 1

Try to find two solutions.

The simplest algorithm is a brute force recursive algorithm with backtracking. Once you have found the first solution, backtrack and look for a second. This is slow but (unlike algorithms that rely on logic alone) it is guaranteed to be able to find all the solutions eventually. Therefore if this algorithm terminates having found only one solution then that solution must be unique.

This will work for easy problems but could take hours or days for harder problems. There are many optimizations you can use if you need more speed.

A simple optimization is to keep track of a candidate list for each square. At each step find the square with the fewest candidates. If there is only one candidate, choose that number, update the grid and the candidates for the other squares, then continue. If there are ever zero candidates you know that a guess you made previously was wrong so you should backtrack.

More advanced optimizations involve looking for patterns which allow you to deduce numbers without making guesses. Here are some examples:

• Techniques For Solving Sudoku
  • Single Position
  • Single Candidate
  • Candidate Lines
  • etc...