Dancing Links pivoting heuristics

MontagFTB

Hi all,

Other than the two mentioned in the Knuth dancing links paper, what other heuristics exist in choosing the best column on which to pivot?

Blessings,
Foster

dukuso

angusj · Site Admin

MontagFTB

dukuso

MontagFTB

Make sure the first 81 columns represent the first 81 cells in the puzzle: if they represent another part of the encoding you may be limiting yourself prematurely. I didn't end up limiting it to the first 81 columns, but I found if you break when you find a row with sz = 1 you get a speed boost. A size of 1 can be found often within the 81 cells (and hence one of the first 81 columns), and increasingly so as other cells are filled.

Blessings,
Foster

dukuso

MontagFTB · Posted: Thu Sep 15, 2005 3:50 pm Post subject:

Sorry, yes, I meant columns with size 1.

According to knuth's algorithm in the dancing links paper the search for the most constrained column doesn't automatically stop at 1. Your implementation might; mine didn't. But it does now.

Hm... I wonder if we could find some way to determine if the column we have selected is the last column of size sz. Then we can increment some size tracker to sz+1, and the next time through the algorithm if we find a column with that size we can now break, as we know we have found the most constrained column. This couldn't be preprocessed as the sizes in the columns are constantly changing... I'll have to think about that one a bit. Thoughts?

Blessings,
Foster

dukuso · Posted: Thu Sep 15, 2005 4:47 pm Post subject:

Foster, can you reformulate :

----------------------------------------
Would it make sense to limit the search range to the columns representing the cells (1..81), and choose the most constrained from those? I'm wondering if those aren't the ones usually chosen by default anyhow, as row/col/box colums will have at least as many as the most constrained cell column...
-------------------------------------

i.e. the last sentence ? Seems that I misunderstood something.
We have 324 columns, 81 for rc,81 for rs,81 for cs, 81 for bs

row,col,block,symbol

let the size of a column be the number of unmarked rows intersecting it

all rows have size 4 anyway, since whenever a column is deleted
all intersecting rows are deleted too.

Now we search for the column of minimum size.
This needn't be a column of type rc, if you meant this.

MontagFTB · Posted: Thu Sep 15, 2005 5:41 pm Post subject:

Lummox JR · Posted: Thu Sep 15, 2005 6:12 pm Post subject:

That inference is fairly trivial to disprove. It's easy to find partially solved boards where in a row, for example, each cell may have 2+ candidates but a particular digit only appears in one of them. And indeed, it's hardly possible to call something a constraint if it's always at least as loose as a different constraint.

In dancing links, finding 1 unmarked row in one of the first 81 columns only reveals a naked single, while the next 243 columns can reveal hidden singles. If you only test the first 1/4 of the columns, you'll basically be forcing your solver into making guesses in situations where the next move is already constrained.

Regarding the idea of breaking after finding the most constrained column: Well, it's possible, but you'd only want to do it in situations where that column had size 0 (i.e., the board is insoluble in its present state). When you find a size 2+ column you want to keep going to find the 1's. And if you find a 1, you'll want to use its information to keep finding 1's. Thus it makes sense--except possibly in a human-like solver algorithm--to loop through all columns to find 1's, not stopping or resetting along the way, and then to repeat the loop again until no more are found. Of course, in a standard DLX implementation you'd always move on to the next step and start the loop from scratch whenever a single was found.

dukuso · Posted: Thu Sep 15, 2005 6:16 pm Post subject:

symbol is one of the 9 digits which go into a cell.

rc: each cell contains exactly one of the 9 symbols
rs: each symbol occurs exactly once in each row
cs: each symbol occurs exactly once in each column
bs: each symbol occurs exactly once in each block

these are the 324 Columns (constraints)

rcs: symbol s goes into the cell in row r and column c

these are the 729 Rows (placements)

placement rcs meets constraints rc,rs,cs,bs
where b is the block defined by row r and column c

now, it can happen that r1s7 has size 1 but all
rc have size >1 :

MontagFTB · Posted: Thu Sep 15, 2005 8:46 pm Post subject: