|
View previous topic :: View next topic |
Author |
Message |
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Mon Oct 17, 2005 6:21 pm Post subject: To shortcut or not to shortcut? |
|
|
I've found that I get varying results with shortcutting certain forms of analysis. For example, my solver will scan for number chains of length 3 to n. In non-shortcut mode, it might find a 3 length chain and remove some candidates, then find a 4 length chain, and do some more removal. When it's done scanning for all the possible chains, because it managed to remove some numbers, it loops back round to the level 1 analyses again.
In shortcut mode, the first time it removes some candidates, it then goes back to level analyses 1 again, not checking for longer chains after the first 'hit'.
I've found that shortcutting seems to produce the better ratings for the puzzles, as it more closely mimics human behaviour. Human solvers will find a number that works in a position, then look for simple pins and implications that the number forces. Non-shortcutting removes more candidates more quickly, but ends up requiring much harder analyses to solve the puzzle. I recently made my solver shortcut every form of analysis, and it has resulted in a better program (for me).
What experiences do the other programmers have with regards to this? I see from testing that the Sudoku Susser uses shortcutting in this way. Does anybody else?
Gaby _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Mon Oct 17, 2005 7:30 pm Post subject: |
|
|
I'm not sure what your "number chains" are.
This is what my solver does:
All eliminations are processed by a queue.
The clues are processed first, their eliminations queued.
Then the queue is processed. Naked singles, hidden singles and pointing pairs are dynamically detected, adding more eliminations to the queue.
When the queue is empty, other techniques are called for.
Naked and hidden subsets are handled by a single recursive method. Whenever a subset is found, this method stops and returns to processing the queue, where the eliminiations for the subset have been placed.
Next in line are digit formations (x-wing, swordfish and other seafood). Again any formation that caused eliminations will return to the queue.
Remote (locked) pairs is next
XY-wing is next (actually a more advanced technique than coloring, but I plan to combine the 2 techniques, using XY-wing output in coloring)
Next is multi-coloring
Single digit template check is next. Maybe removed when my coloring enhancements are operational.
The remaining test are only performed when all clues are fully entered and processed and the puzzle has not been completely solved by earlier methods.
Uniqueness test. This method will, when eliminations were made, return to the queue.
When the solver tried every weapon in its arsenal, and the puzzle is still not completely solved, a backtracking solver is called for the remainder of the puzzle. This is the only method that does not return to the queue. Either it can solve the puzzle or declare it invalid.
Conclusion:
Shortcutting is better for performance, because the more basic techniques require less searching. It also helps you to assess the difficulty level. When you find an X-wing and 2 swordfishes, you may give a puzzle a high rating, where shortcutting may reveal that the X-wing broke the puzzle, leaving singles only to complete it.
To improve your performance even further, keep track of what has been changed since the last time you performed a search. Using shortcuts causes your solver to revisit the same methods after each elimination. For example, keeping track changes in candidate count per digit allows you to skip coloring that digit when nothing has changed. |
|
Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|