Does the order the patterns (methods) are applied matter?

kranser

Do most programs start out checking for one pattern/solving method and check all rows, columns and boxes for this method and then go on to the next method?

If so, is it best to start with the easiest methods first (candicates, subsets), or is it best to start with the difficult ones (swordfish, XY, X-wing) first? Does it matter?

Does using the easiest methods first restrict or enhance the ability to find a swordfish pattern later on?

Kranser.

gaby · Posted: Thu Aug 25, 2005 10:14 am Post subject:

My program starts by trying all the really simple techniques first, as they're the most benefit for the least execution time. Only when it gets stuck on those does it try the harder techniques. Some of the harder techniques involve recursive algorithms, so reducing the search space by a small amount can have a larage effect on the amount of processing required for a recursive method.

I haven't really done much testing involving putting the methods in different order, but I have them applied in order of algorithmic complexity. I think sacrificing the ability to identify a swordfish later on is offset by the ability to do a fast forcing chains analysis instead.

Perhaps some experimentation is in order...

Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

dukuso · Posted: Fri Aug 26, 2005 8:28 am Post subject:

however, I assume that the techniques do commute ?!
(I haven't tried these yet)

or is it possible that some puzzle can be solved with some set of techniques
in one special order but cannot be solved when the
order of the techniques is changed ?

discarding some possible effects on the running time

jbum · Posted: Sat Sep 24, 2005 6:16 am Post subject:

It depends on what you're trying to accomplish. If you're trying to reproduce how a human might solve it, it is better to use simple to understand techniques before hard to understand techniques. I use this kind of system I am trying to understand whether a puzzle "requires" a particular technique, such as XY-Wing.

If you're trying to solve the puzzle quickly, it is better to use techniques that solve patterns that have a statistically high likelihood of occuring, and which are more efficient, first.

So while a human might look for X-Wing first, it is more effective to look for XY-Wing or Turbo-fish first, since these occur more often.
_________________
http://www.krazydad.com/

Ruud · Site Admin

For me. the following sequence works best:

1. Eliminate candidates blocked by an entry.
2. Update hashes and counters for cells, rows, columns and boxes.
3. Use the counters to detect naked and hidden singles.
4. Check the minirows and minicolumns for locked pairs and triples.
5. Check the r/c/b hashes for naked and hidden subsets.

All additional blocks from 3, 4 and 5 are placed on a queue.

6. Process the queue and repeat 2 through 6 until the queue is empty.
7. Check for advanced patterns (X-Wing, Swordfish, remote pairs, etc)
8. For each pattern found, put eliminated candidates on the queue (goto 6)

When queue is empty, no more patterns found, puzzle not yet solved:

9. Use coloring, forced chains, templates (see specific topic)
(again, all results from this step are queued)

Still no solved puzzle?

10. Use the selected brute-force solver. There are currently 4 built in my program:
- Trial & Error (slow but very human)
- Dancing Links (extremely fast and elusive)
- Template comparison (little slower, but able to reveal relationships between eliminated candidates and the cells that cause it)
- Recursive rows (a technique that works on a row-by-row basis, similar to dancing links, but without the requirement of the specific columns & rows. it works on the data structures already in place for other techniques)

11. Hide all these results and let the user solve the puzzle himself Smile