somebody tried this? "Dancing templates"

soduko

Reading about dancing links (DLX) I suddenly realised that you can also combine dancing links with templates.

the rows (placements) becomes the templates+ symbol (a big number) {9* (6^6), I cannot find my calculator}

While the number of collums / constraint become much smaller number (90 vs 324) ( only the RC constraints and a collumn/ constraint per symbol)

I am not sure if it will be quicker than the "normal DLX" but it has a lot of efficiency in it, the depth of the search will be reduced to 9, (vs 61- 81) (only nine templates make a soduku) and maybe even more interesting the test of constraints can be done bitwise (there are only 90 of them).
Against it are the very much lager number of rows (9 * 6^6 vs 729) and more constraints per row.(10 vs 4)

maybe there are even more efficienties possible.
(I haven't said anything about grouping the templates by symbols yet)

I will add more mathematical data as it becomes available, (when i find my calculator)
But i think that my computing power is not up to this way of solving soduko. (and i am using basic instead of more capable languages)

But maybe yours is...

Please try.

dukuso · Posted: Fri Dec 09, 2005 6:29 pm Post subject:

yes, a sudoku solution is just a disjoint union of 9 out of
the 46656 templates and thus an exact cover problem
with 46656 rows and 81 columns. That is for the
empty grid.
Now given a sudoku with clues, select those out of the
46656 templates, which have only clues of one value
(=digit=symbol) in it.
Any solution of the sudoku must be a disjoint union of those
templates and vice versa.

I don't think this method will be very effective, though.
But it's worth trying. Should be easy to test...

I don't see, why you think you need 9*46656 rows and 90 columns

soduko · Posted: Fri Dec 09, 2005 8:06 pm Post subject:

dukuso · Posted: Sat Dec 10, 2005 5:10 am Post subject:

you are right, it should be done with 90 columns and 46656*9 rows
for the empty grid.
You could try 46656 rows and 81 columns but then you must filter the
output, since some templates might contain the same symbol.
I tried it, it's very slow while your method found the solution
in 5sec. - still much slower than the normal method.

When each symbol occurs as a clue, then after the reduction
there can't remain more than 46656 rows.

I tried this sudoku:
7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5...........
and 12854 rows remained after the reduction.

Further reductions due to forced placements are probably useless
since the algo would do these anyway.

Ruud · Site Admin

dukuso · Posted: Sat Dec 10, 2005 12:46 pm Post subject:

yes, it's much slower.
And probably not feasable for larger sudokus.
How many templates are there for 16*16 ? Probably too many.

The number of rows is not the main problem,
when converting sudokus to SAT-instances you
can get very large files too (before reducing due to clues)-
yet this is the fastest known method.

The templates method could become more intesting
when you add further constraints, like in 3doku
or magic sudoku.

soduko · Posted: Sat Dec 10, 2005 6:27 pm Post subject:

hello Dusoku and Ruud

Dusoku wrote:

dukuso · Posted: Sun Dec 11, 2005 3:00 am Post subject:

I did include all those templates as rows in the matrix, which
just only hit symbols of one type. They needn't hit all the symbols
of that type.

That's useless, I changed that.
Now the matrix has typically 500 rows on hard sudokus,
but sometimes upto 7000.
Speed does compare well with the convential method,
but I generated the matrix with another program,
that time was excluded.

I'm wondering whether that method is competitive for
25*25 sudokus or QWHs ?
Probably not, but it's worth trying...

or maybe a combined method: generate one subproblem
for each template for the most common symbol