Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Non-determinism in Knuth's Algorithm X

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
Jack

Joined: 19 Oct 2006
Posts: 1
:

Items
PostPosted: Thu Oct 19, 2006 2:37 pm    Post subject: Non-determinism in Knuth's Algorithm X Reply with quote

When determining whether or not there is a unique solution to a particular grid, should the non-deterministic step in Algorithm X be changed to deterministic in order to ensure that all possible solutions are found?

Thanks,

Jack
Back to top
View user's profile Send private message
brassbandit

Joined: 12 Oct 2006
Posts: 6
:
Location: Liverpool L8

Items
PostPosted: Thu Oct 19, 2006 2:48 pm    Post subject: Reply with quote

It doesn't matter - all solutions will be found whichever route you take, it's just that the determinstic route shortens the path by concentrating on searches with few choices, and reducing the number of dead ends you're likely to come up against.

IIRC there's a pretty picture of the search tree in Knuth's paper.

In any case, you want to stop searching after two solutions have been found, as you've proved the solution isn't unique by then.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron