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   

To shortcut or not to shortcut?

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
gaby

Joined: 02 Jul 2005
Posts: 120
:

Items
PostPosted: Mon Oct 17, 2005 6:21 pm    Post subject: To shortcut or not to shortcut? Reply with quote

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
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Oct 17, 2005 7:30 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving 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