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?

Postby RaiderFan92 » Sun Nov 09, 2008 11:16 am

How can you tell if a sudoku has a unique solution?
RaiderFan92
 
Posts: 7
Joined: 30 April 2008

Re: Unique Solution

Postby m_b_metcalf » Sun Nov 09, 2008 11:57 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8365
Joined: 15 May 2006
Location: Berlin

Postby Luke » Sun Nov 09, 2008 12:18 pm

Go to Scanraid and load your puzzle. Then click on "Solution Count" and you'll soon have your answer.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby m_b_metcalf » Sun Nov 09, 2008 1:14 pm

Luke451 wrote:Go to Scanraid and load your puzzle. Then click on "Solution Count" and you'll soon have your answer.

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

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8365
Joined: 15 May 2006
Location: Berlin

Postby Luke » Sun Nov 09, 2008 4:10 pm

How would you go about counting the number of solutions?
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby Glyn » Sun Nov 09, 2008 4:54 pm

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

Postby m_b_metcalf » Tue Nov 11, 2008 12:35 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8365
Joined: 15 May 2006
Location: Berlin

Postby Glyn » Tue Nov 11, 2008 1:06 am

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

Postby m_b_metcalf » Tue Nov 11, 2008 1:34 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8365
Joined: 15 May 2006
Location: Berlin


Return to General