729x324 exact cover 3D and S-DLX proposal

Bob Hanson

In this posting I offer two suggestions:

1) A new 3D way of looking at the exact cover "matrix"
2) A possible optimization of DLX for Sudoku -- S-DLX

1) A new 3D way of looking at the exact cover "matrix"
----------------------------------------------------------------

It occurred to me after reading Knuth's paper again and writing
http://www.stolaf.edu/people/hansonr/sudoku/exactcover.htm that:

a) There's a heck of a lot wasted white space here
b) Sudoku isn't pentominos. All the pieces are identical
c) The DLX algorithm, though proposed for solving exact cover
problems, which are generally expressed in terms of a 2D matrix,
really doesn't require this. It's just a set of multiply linked nodes that,
hen depicted this way actually look pretty messy.
d) Knuth wasn't thinking Sudoku -- he was being far more general. He
proposes a single optimization strategy -- "start with 2-valued constraints"
-- but doesn't consider puzzle-specific optimizations.

OK, so putting 2 and 2 together.... Consider the basic 729x324 matrix:

dukuso · Posted: Fri Dec 23, 2005 9:11 am Post subject:

I'm afraid most of your sudoku-specific ideas to "improve"
the DLX are not efficient, i.e. will not speed up the search.

While those ideas which do result in faster solving
are not sudoku-specific and work e.g. for QWH as well.

gsf · Posted: Fri Dec 23, 2005 3:29 pm Post subject:

9x9 sudoku may be too simple to expose the combinatorial explosion of higher order problems. As problem size increases so do the number of backtrack nodes, and then the per node computations overwhelm everything else. This is where techniques like forward checking and arc consistency come into play. They attempt to efficiently reduce the number of backtrack nodes by using the backtrack tree itself to flush out physical properties rather than computing those properties directly. For example, a simple one level forward check handles naked pairs without backtracking and provides the info needed to pick the best candidate(s) to backtrack on.

I don't use dancing links. For 9x9 sudoku how many link operations are required to assign a value to a cell and then retract that assignment? Are any other computations required along with the retraction?

dukuso · Posted: Fri Dec 23, 2005 3:44 pm Post subject:

I have about 500 placements per millisecond, that's
about 1000 CPU-cycles per placement, including search for
the best constraint, updating all the counts of neighbors,
deleting (marking as used) rows and columns, and later
un-placement when backtracking

gsf · Posted: Fri Dec 23, 2005 3:55 pm Post subject:

After posing that question I realized almost any answer will be apples to oranges. The candidate selection strategy and other backtrack optimizations will skew per-node costs beyond comparison. For instance, despite claiming that per-node computations should be kept to a minimum, my solver only has 5 backtrack nodes for the top1465 9x9 sudoku, so my cycles per node are way up there.