Hard puzzle for DXL.

jbum · Posted: Sun Aug 14, 2005 7:22 pm Post subject: Hard puzzle for DXL.

I've written two solvers, a fast one based on Knuth's 'dancing links' and a slow one for estimating puzzle difficulty for humans. I'm interested in finding ways to use the metrics I can get from DXL (dancing links) to estimate puzzle difficulty.

The dancing links method solves pretty much any solvable sudoku in just a few milliseconds. It does find some puzzles harder than others in the sense that simple puzzles reduce down to a single choices (dxl columns with a length of 1) whereas more difficult puzzles tend to generate more instances where the smallest dxl column is > 1.

Using this metric, the hardest puzzle posted on this board for DXL has been rubylip's, which generates 51 such dxl columns with a length > 1 - meaning some form of 'what-if' would be required 51 times. It's possible this can be reduced by transposition.

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

yes, these two are also hard for me, although there are harder
ones in my list for my solver.

the first one required 78 choices of DLX-columns with more than 1 entry
and 1102 placements in total

the second 62 and 791.

It just depends how the sudoku is oriented and how your matrix
is ordered.
You can do random equivalence transformation of the sudoku
or random permuting of the rows and columns in the
exact-cover matrix and you may see completely different
results in some cases.

Guenter.

jbum · Posted: Mon Aug 15, 2005 6:25 am Post subject:

Yes, I agree. At some point I'm going to iterate thru the transliterations so I can record the lowest difficulty...
_________________
http://www.krazydad.com/

jbum · Posted: Mon Aug 15, 2005 9:33 pm Post subject: More hard puzzles

I've been working on getting my puzzle generator to search for hard puzzles (identifying puzzles that generate a lot of branching in the depth
first search).

I generated these last night, they are sorted by estimated difficulty with the harder ones at the top.

Note that my generator always generates puzzles with 1-9 in order in the top row. This helps speed up puzzle generation. If preparing these puzzles for humans (e.g. my wife), I randomly transliterate the numbers with a perl script.

Merri · Posted: Mon Aug 15, 2005 9:43 pm Post subject:

To compare against pure computer processing speed with some brute force approach, here are some results:

jbum · Posted: Mon Aug 15, 2005 9:48 pm Post subject: thanks merri

Cool - thanks a lot. It looks like I sorted them roughly accurately.

If you can point me to a thread that contains some of those 6 ms monsters, I'd like to check 'em out.

Thanks!
_________________
http://www.krazydad.com/

Merri · Posted: Mon Aug 15, 2005 10:00 pm Post subject:

Actually not, if you check the file names they're pretty much "random" and not in any special order at all when compared to yours. The 6 ms "monsters" are probably easier for a non-backtracker approach. However, here are some which take more than 4 ms:

.......473..5............1.7.9...6......1..........2.....2..7.5.41..8....3.......
....4.61.2.53...........9..4......82.6..1.............7..5.2......8..1...........
....61....9.....3..........6.1...7.....75..8.4...........2..4.9.5.3...........1..
....7.51.2.63...........8..4......92.5..1.............6..4.2......6..1...........
..5.4....7......2......1......5..3.....6...7..1.......8..2.3.......5.1.4......6..
2..4..1...6..5.............3..8.......42............76....71....5..6......8...3..
2..4..1...6..5.............3..9.......82............76....71....5..6......9...3..
37.4........7...5.........1.4....2......8...6....1.......2..7..6......4.1.8......

These are in no particular order, just the TOP 8 of the latest benchmark run. My times vary, it would be better if I had a difficulty rating instead of a timing code, but can't be helped: taking part in a contest with the code. You can find a compiled version here.

You can find those and 7603 puzzles more at http://www.csse.uwa.edu.au/~gordon/sudoku17 - these are all 17 clues puzzles.

jbum · Posted: Mon Aug 15, 2005 10:04 pm Post subject: Thanks

Thanks again. Smile

Clearly our solvers are sensitive to different things. My DXL solver is also a backtracking (depth first search) solver, but it solves this set about
twice as fast as the ones I posted previously.

My intuition is that the dancing links algorithm views the puzzles in a very
odd way... Smile

The hardest ones in your list for me (#2 and #4) generate 9 and 8 backtracks, respectively, while all the ones in my list were generating 30+
backtracks in DXL. Some of the puzzles in your list generated 1 or 0 backtracks.

Interesting...

- Jim
_________________
http://www.krazydad.com/

dukuso · Posted: Tue Aug 16, 2005 3:05 am Post subject:

Merri's hardest are indeed so easy for me, that I already
wondered whether he posted the right sudokus :

1 sol. 64 nodes 0 guesses 15/91msec
1 sol. 222 nodes 23 guesses 70/91msec
1 sol. 64 nodes 0 guesses 85/91msec
1 sol. 270 nodes 21 guesses 145/91msec
1 sol. 93 nodes 4 guesses 165/91msec
1 sol. 64 nodes 0 guesses 180/91msec
1 sol. 64 nodes 0 guesses 195/91msec
1 sol. 70 nodes 1 guesses 210/91msec

or 1000 runs with randomized permuting of rows and columns of
the exact-cover matrix:
1000 sol. 64000 nodes 0 guesses 110/91sec
1000 sol. 254647 nodes 19267 guesses 265/91sec
1000 sol. 64000 nodes 0 guesses 375/91sec
1000 sol. 261019 nodes 21049 guesses 525/91sec
1000 sol. 76725 nodes 2207 guesses 640/91sec
1000 sol. 64000 nodes 0 guesses 750/91sec
1000 sol. 64000 nodes 0 guesses 855/91sec
1000 sol. 73606 nodes 1292 guesses 970/91sec

jburns list with 1000 randomized runs:
1000 sol. 375654 nodes 25162 guesses 175/91sec
1000 sol. 257631 nodes 16583 guesses 325/91sec
1000 sol. 211263 nodes 16759 guesses 460/91sec
1000 sol. 382634 nodes 22890 guesses 635/91sec
1000 sol. 130860 nodes 5175 guesses 760/91sec
1000 sol. 147835 nodes 7316 guesses 885/91sec
1000 sol. 236614 nodes 16593 guesses 1030/91sec
1000 sol. 322571 nodes 17719 guesses 1190/91sec
1000 sol. 204597 nodes 12290 guesses 1325/91sec
1000 sol. 189278 nodes 11842 guesses 1460/91sec
1000 sol. 170205 nodes 11033 guesses 1590/91sec
1000 sol. 247389 nodes 13812 guesses 1735/91sec
1000 sol. 231401 nodes 13036 guesses 1880/91sec
1000 sol. 147201 nodes 8869 guesses 2005/91sec
1000 sol. 272882 nodes 17727 guesses 2160/91sec
1000 sol. 177931 nodes 8312 guesses 2290/91sec
1000 sol. 278192 nodes 16798 guesses 2440/91sec
1000 sol. 182743 nodes 12197 guesses 2575/91sec
1000 sol. 397933 nodes 32238 guesses 2755/91sec
1000 sol. 106808 nodes 3647 guesses 2870/91sec
1000 sol. 148185 nodes 7333 guesses 2995/91sec
1000 sol. 227020 nodes 13012 guesses 3140/91sec
1000 sol. 266684 nodes 14423 guesses 3290/91sec
1000 sol. 250636 nodes 14521 guesses 3435/91sec
1000 sol. 275605 nodes 16662 guesses 3585/91sec
1000 sol. 266591 nodes 15609 guesses 3735/91sec
1000 sol. 138951 nodes 6323 guesses 3860/91sec
1000 sol. 173080 nodes 9732 guesses 3995/91sec
1000 sol. 117516 nodes 3381 guesses 4110/91sec
1000 sol. 214381 nodes 14026 guesses 4250/91sec
1000 sol. 273535 nodes 17396 guesses 4405/91sec
1000 sol. 188816 nodes 9898 guesses 4540/91sec

how did you make them ? how long did it take ?
Can you give the nodes or timings for them, so I
can compute the correlation coefficent between
our rating ? (mine vs. Merri's was earlier
computed as 0.4, but maybe with an older version)

Here are the hardest for my solver: http://magictour.free.fr/top100

jbum · Posted: Tue Aug 16, 2005 5:36 am Post subject:

> how did you make them ? how long did it take ?

My puzzle generator generates puzzles pretty quickly (a hundred
in a few seconds). If I filter for hard puzzles ( with > 20 mults - see below) then it generates one or two every minute or so.

My generation algorithm is based on a modified version of my DXL solver.

1) I start with a puzzle that has 1-9 in the top row, and the rest blank.

2) I solve it, stopping prematurely when I hit the first solution (there will
be many solutions). While solving it, I select nodes randomly (but do so
in such a way so that generating the puzzle doesn't take a long time).

3) I remove numbers in symetrical pairs, until I can't find a pair I can remove (without making more than one solution). In one version, when I remove these pairs, I select pairs that lead to harder puzzles. This slows down the puzzle generation, but may produce somewhat harder puzzles.

4) When the puzzle is done, I transliterate the numbers randomly, so that
it doesn't have 1-9 in the top row. Sometimes I skip this step, if I want
to compare the puzzles to each other for patterns.

> Can you give the nodes or timings for them

The timings aren't really relevent, since our computers are different speeds.

Here are some new puzzles I generated today (the first few are harder than the ones above), which include some stats. Not all of these are transliterated.

Simes · Posted: Tue Aug 16, 2005 7:03 am Post subject:

jbum · Posted: Tue Aug 16, 2005 7:07 am Post subject:

Sorry, I mean I remove pairs I *hope* will lead to harder puzzles. I do this by testing the removal of all possible pairs, and then choosing the pair that produced the most backtracking.

This slows down puzzle generation however. I'm not yet convinced that simply producing random puzzles (which is much faster) and then filtering the difficult ones out isn't just as effective.
_________________
http://www.krazydad.com/