| View previous topic :: View next topic |
| Author |
Message |
| Jack
| | Joined: 19 Oct 2006 | | Posts: 1 | | : | |
Items |
|
 Posted: Thu Oct 19, 2006 2:37 pm Post subject: Non-determinism in Knuth's Algorithm X |
 |
|
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 |
|
 |
| brassbandit
| | Joined: 12 Oct 2006 | | Posts: 6 | | : | | Location: Liverpool L8 |
Items |
|
| Posted: Thu Oct 19, 2006 2:48 pm Post subject: |
|
|
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 |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
