How can you tell if a sudoku has a unique solution?

Everything about Sudoku that doesn't fit in one of the other sections

How can you tell if a sudoku has a unique solution?

How can you tell if a sudoku has a unique solution?
RaiderFan92

Posts: 7
Joined: 30 April 2008

Re: Unique Solution

RaiderFan92 wrote:How can you tell if a sudoku has a unique solution?

Method 1 (recommended): count the number of solutions. If the there's only one you're home and dry. (You can stop counting at two.)

Method 2 (for the bold): Find one solution. In that solution find all the unavoidable sets. For each unavoidable set check that at least one clue covers that set.

HTH

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 9058
Joined: 15 May 2006
Location: Berlin

Luke
2015 Supporter

Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Which begs the question as to how Scanraid knows the answer!

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 9058
Joined: 15 May 2006
Location: Berlin

How would you go about counting the number of solutions?

Luke
2015 Supporter

Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

RaiderFan92 It depends why you want to know? If it is purely to know that you can apply uniqueness methods with a degree of confidence to a grid you've been given then most solvers will incorporate such a facility.
On the other hand if you are programming a generator then Mike's guidance towards a brute force Method 1 is best, you will want the test incorporated into the software because it is going to get used a lot.
Glyn

Posts: 357
Joined: 26 April 2007

Glyn wrote:On the other hand if you are programming a generator then Mike's guidance towards a brute force Method 1 is best, you will want the test incorporated into the software because it is going to get used a lot.

If by 'best' you mean simplest to implement I agree. If, on the other hand, you mean fastest, then this is definitely not true, especially for demonstrating that candidate puzzles with low clue counts are minimal, or for testing whether they have any solution. The fastest solver is one that doesn't get called.

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 9058
Joined: 15 May 2006
Location: Berlin

Mike Thanks for your comments re the two approaches to examining uniqueness. Perhaps the Isolated Subpuzzles thread might interest you with respect to Method 2.

I've now established that RaiderFan92 is a pen and paper solver, in which case either a quick pass through one of the solver programs or trusting the source of the puzzle is the most sensible.
Glyn

Posts: 357
Joined: 26 April 2007

Luke451 wrote:How would you go about counting the number of solutions?

Inside my solver I remove the stop at 'number of solutions equal to two' and let it find them all, and print that number at the end. This feature is useful as a diagnostic test for demonstrating that a solver really works.

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 9058
Joined: 15 May 2006
Location: Berlin