should the links dance ?

dukuso · Posted: Fri Jul 29, 2005 1:03 pm Post subject: should the links dance ?

when you solve the sudoku by computer using the
729*324 binary exact-cover matrix,
(which is apparantly the best and easiest method !)
should you use the "dancing links" method as described by Knuth
or should you just use static pointers to the 2916 ones in the matrix,
4 for each of the 729 rows and 9 for each of the 324 columns ?

I use the second method and I mark some rows and columns as "used"
during the solving process.
This has the disadvantage, that I repeatedly
have to walk through a list of columns or rows, although most
of them are already marked as "used" .
On the other hand I don't waste time to compute links and they
are not allowed to dance, so my program remains clearer and easier
to handle.

But which method is supposed to be faster ?
Can we do some benchmarks ?

Guenter.

jbum · Posted: Sun Aug 14, 2005 11:21 pm Post subject:

I think the dancing links method is probably more efficient, since there is much less time spent in the deeper depths of the tree walking over zeros. Although time is spent managing links, there is no time spent setting ones & zeros (the matrix does not actually store 1s and 0s- the presence of a record is a "1"), so I suspect the maintainence is equivalent.

But I'm not sure.

At some point in the next few days, I'm going to do a benchmark comparing the C exact-cover code you posted here:

http://www.setbb.com/phpbb/viewtopic.php?t=119&mforum=sudoku

with a C version based on Knuth's 'dance.w'.

My Java version is based on Knuth's method, but it is probably slower than your C version, due to being in Java. It will be interesting to compare apples to apples. My java version uses recursion instead of gotos, and it is probably faster to use gotos, as Knuth does in his C implementation.
_________________
http://www.krazydad.com/

dukuso · Posted: Mon Aug 15, 2005 5:56 am Post subject:

the most time-critical part seems to be the
marking and unmarking of the used rows and columns
resp. the updating of the links.

Whether you use gotos or calls, that should not matter a lot here.

jaap · Posted: Mon Aug 15, 2005 8:28 am Post subject:

dukuso · Posted: Mon Aug 15, 2005 9:23 am Post subject:

yes, I'm doing the same.
You needn't store the whole matrix.
I gave up on this since I optimistically left room
for sudoku-sizes upto 64*64, and that would
give matrices of 4 gigabit !

But I will probably never be able to solve random sudokus
of size 36*36 or larger.

Guenter.

jbum · Posted: Mon Aug 15, 2005 9:24 pm Post subject: links / no links test results

Hi Guenter,

I ported my Java DXL implementation to C, and wrote a test program that solves 7000 randomly generated puzzles using both DXL, and the code you posted previously.

For your code, I removed the printf, and split it into a one-time initialization section (which doesn't count for time) and a solver which can be called repeatedly with a puzzle string (basically, the same as my DXL code is structured).

On my old slow Linux box, your code solves 612 puzzles a second.

The DXL code solves 1977 puzzles a second. So basically a little over
3x faster.

For a smaller test set of "hard" puzzles (that generate a lot of backtracking in DXL), the DXL code is 6x faster.

You mentioned in another thread that you are working on a 5x speed improvement, so perhaps you've passed DXL - on the other hand,
if the improvements apply to DXL equally, then both would benefit.

This is a very slow machine I'm testing on. No doubt you are getting faster times on your own box. I'll do some tests tonight on a faster machine I have at home.

If you want a copy of the test-code, let me know and I'll either email it to you or post it here. jbum [at] jbum.com

- Jim

EDIT: I modified the message to reflect a test run with a larger, more random sample of puzzles.
_________________
http://www.krazydad.com/