Dancing Links - Can it go even faster?

Ruud · Site Admin

Hi,

I would like to open a new discussion here, on the topic of dancing links. I have used this code posted by antony as the basis for the DLX implementation in Sudo Cue, but I did make a few modifications to speed it up a little more.

Maybe other people have found different ways to speed up the process, and I am very interested in your opinions.

These are the parts I optimized:

1. The "header" nodes (columns) are linked according to their size. For each size (1 through 9) there is a root node. These root nodes are linked with the Up/Down links. Finding the best column is now done in only a few steps. No need to maintain size, just relink a node to the up/down peer of its root node.

2. Each row has 4 associated nodes. The structure may be simpler connecting them with left-right links, but performance is better when each node has direct links to the other 3 nodes. No left-right loops with end-of-loop test are required.

3. When the clues are "loaded", the program will already "cover" the affected columns. DLX will not gain much, since the search is already optimized. Still, a few lines of code are squeezed out this way.

Ruud.

dukuso · Posted: Wed Nov 16, 2005 7:06 am Post subject:

how much speed do you gain with 1),2),3) ?

The problem is, what to do on ties, when there are several columns
of size 2, but none of smaller size.

Have you tried 16*16 ? I think 9*9 is too small to
estimate the effect on algorithm improvements.

I implemented the Row/Column <--> Block interaction
yesterday. (rule JAAP1, N(c1)<N(c2), r in N(c2)-N(C1)
then r can be removed)

but it was slower than before. Even if I could test this in zero time,
it would only give 15% more speed on 16*16.
I only did it for columns of size 2, though.

I got 6fold better speed on 16*16 with a _bug_ recently, I still don't
really understand why. I attach the C-code below.
The idea is to remember which choices were better on ties
and then reuse this info.

Nick70

[quote="Ruud"]1. The "header" nodes (columns) are linked according to their size. For each size (1 through 9) there is a root node. These root nodes are linked with the Up/Down links. Finding the best column is now done in only a few steps. No need to maintain size, just relink a node to the up/down peer of its root node.[/quote}
This is an interesting suggestion and I tested it, but the speed decreased instead of increasing.

I think for higher order sudokus it might be an improvement, because you are removing the scan of the available columns to find the shorter one. For 9x9 sudoku, however, doing that scan seems to be less expensive than unlinkking/relinking the columns every time you unlink/relink a row.

soduko · Posted: Tue Nov 22, 2005 2:18 pm Post subject:

I was thinking about the following speed up:

Before the trail and error fase.

If a test (Constrait) can only be satisfied by two (valid) placements :
(call them P1 and P2)
All placements that make P1 false will be followed by P2
All placements that make P2 false will be followed by P1
(for explainations sake this are the eliminating placements)
P1 and P2 are no options to start with in the T&E fase.

An example
the Test C8V9 can only be satisfied by
P1 R1C8V9 and
P2 R2C8V9

P1 is made false by

R1C1V9 till R1C9V9
R1C8V9 till R9C8V9
ect
(the squares of this are always the same for every square and can be stored in an array before starting the solving proces)

All these placements will have the followup placement of p2 R2C8V9.

the same applies for the other placement.

P1 and P2 can be eliminated from the trail and error fase.
(they are now implied in all the tests resulting from the eliminating placements)

You can also test the eliminating placements them selves

If 2 followups from the same placements are contradictionary the placement is false and can be removed.

ect, ect.

Hopes this makes it clear.
Now i must find time to change it in a working program...

dukuso · Posted: Wed Nov 23, 2005 5:37 am Post subject:

>was thinking about the following speed up:
>
>Before the trail and error fase.

where is it

>If a test (Constrait) can only be satisfied by two (valid) placements :
>(call them P1 and P2)
>All placements that make P1 false will be followed by P2

a plavement Q "makes P1 false" iff A-P1-Q has no solution ?
(A is our exact-cover-matrix)
isn't it equivalent to "Q in N(N(P1))" and to "P1 in N(N(Q))" ?

but what means : "will be followed by P2" ?

>All placements that make P2 false will be followed by P1
>(for explainations sake this are the eliminating placements)
>P1 and P2 are no options to start with in the T&E fase.

?

>An example
>the Test C8V9 can only be satisfied by

what's V ?

>P1 R1C8V9 and
>P2 R2C8V9

OK, V must be symbol = digit

>P1 is made false by
>
>R1C1V9 till R1C9V9
>R1C8V9 till R9C8V9
>ect

OK. It's N(N(P1))

>(the squares of this are always the same for every square

squares=placements=rows or squares=cells ?

> and can be stored in an array before starting the solving proces)

empty sudoku has |N(N(r))|=29 for each r.
They can always be easily addressed, even without initially storing them.
When you store them, there could be problems when the links start dancing.

>All these placements will have the followup placement of p2 R2C8V9.

what you mean with followup placement ?

>the same applies for the other placement.
>
>P1 and P2 can be eliminated from the trail and error fase.
>(they are now implied in all the tests resulting from the
> eliminating placements)

whenever placement p1 is chosen, we delete p1,N(p1),N(N(p1)).
You can calculate N(N(p1)) for each p1 in advance, but I can't see
why this should help. Just walking through N(p1) and then N(N(p2))
should have almost same speed

>You can also test the eliminating placements them selves
>
>If 2 followups from the same placements are contradictionary
> the placement is false and can be removed.
>
>ect, ect.
>
>
>
>Hopes this makes it clear.
>Now i must find time to change it in a working program...

better spend time on thinking what to do on ties, when
several columns c have #c=|N(c)|=2 ...

We might consider |N(N(c))| or |N(N(N(c)))| ,... although
I would only check them occasionally , so to concentrate on regions.
E.g. in samurai you would concentrate on one of the 9*9 and not
swap the 9*9s on each move and concentrate on another 9*9 at each move.

Dancing links usually doesn't know about these global connections,
it only sees the next neighbors N(c),N(r).

If one of the 9*9s is already half-full and another one is just
only half-full in one column, a human would probably first try
to complete the first one.
But how can we tell this to the computer ?

Or in larger sudokus, when clues are gathered in certain regions,
a human can spot this immediately.
But it's hard to implement, so most programs will presumably fail
to recognize this.

soduko · Posted: Thu Nov 24, 2005 10:49 pm Post subject:

Sorry

I realised that my method has nothing to do with DLX

It is more a way of seeing sudoku as an exact cover problem.

But still to reply to your reply (maybe it is still usefull)

dukuso · Posted: Thu Nov 24, 2005 11:38 pm Post subject:

doesn't it result in the same algo, just some local
deep-first replaced by some breadth first, so to say ?

it could be faster if we can use 128-bit masks to
mark N(N(r)) as used

(using marked rows and columns instead of dancing links)

soduko · Posted: Fri Nov 25, 2005 10:56 am Post subject:

Ruud · Site Admin