The New Sudoku Players' Forum

[Mathimagics]

I downloaded an implementation of DLX in VB6, and was generally impressed with its performance. For example, it solved an 8-clue Jigsaw 100 times faster than my old solver. The region map (jigsaw) is shown first, followed by the givens:

Code: Select all

111112222 133411152 334466652 344667752 346687552 346887592 346877599 348879559 888779999

.....1... ......2.. .......3. 4........ .5....... ..6...... ...7..... ....8.... .........


But when I fed it the following puzzle it went off into some kind of fugue state from which (hours later) I am still awaiting its return:

Code: Select all

111111222 113334422 313344422 333544422 555546666 555566667 888899967 888999777 889997777

123456... 78....... .9....... ......... ......... ......... ......... ......... .........


Now this puzzle has in fact many solutions, and my old solver finds the first one in milliseconds, so I can't quite grasp why DLX should have such a problem with it. Convinced that I had introduced a bug, I downloaded a C version of a DLX implementation, only to discover it behaved in exactly the same way.

[blue]

Mine gets hung up on that one too.
It takes 8.25 seconds to solve the empy grid.
On the puzzle, it ran for >5 minutes, before I killed it.

Edit: For the first one, it hangs on the empty grid, and takes ~25 milliseconds for the puzzle.

[Mathimagics]

I'm glad its not just me! I left it running while I slept. It took 5 hours.

So it appears to be a conditioning problem. DLX is fine as long as the constraints are adequate, but give it a suficienly vague specification and it has conniptions.

I was hoping to use the DLX solver as a GDL testing tool, ie given a GDL (region mapping), does it have a resolution? In 99.99% of cases, DLX is far superior to my "traditional DFS" solver. This includes its ability to determine that a GDL has no solution.

But this exception is a real killer ... I will have to use both solvers in tandem, with bailout conditions.

If I feed DLX a better set of givens it works fine, but in this context I obviously don't have a better set, that's why I'm asking DLX!

Curious ...

[Mathimagics]

DLX seems to be extremely sensitive to the nature of the initial clues. Since I don't know a grid solution in advance, I only have 3 choices for the givens:

• a complete region

• a complete row

• a complete column

DLX times for first solution:

• region 1: 20,000s

• row 1: > 6000s (abandoned)

• row 2: > 1200s(abandoned)

• row 3: > 1200s(abandoned)

• row 4: .007s

• row 5: .007s

• row 6: .007s

• row 7: .007s

• row 8: .009s

• row 9: .009s

• col 1: 1200s

• col 2: 26s

• col 3: .007s

• col 4: .007s

• col 5: 2s

• col 6: .007s

• col 7: 315s

• col 8: .007s

• col 9: .007s

So we have a time range of 7 milliseconds to 20 kiloseconds!

[Serg]

Hi, Mathimagics!

DLX seems to be extremely sensitive to the nature of the initial clues.
. . .
So we have a time range of 7 milliseconds to 20 kiloseconds!

Maybe the reason is that all pure backtracking algorithms are strongly sensitive to initial clue patterns. In some cases contradictions can be found too slow, by filling almost all grid cells. This problem can be solved by adding to the algorithm searching for singles. It stabilizes speed of backtracking, reducing dependence on initial clues. JasonLion recently wrote about it in the thread A fast C++ Solver. I came to the same conclusion when I was developing my own backtracking Sudoku solver years ago. Interesting that (naked and hidden) singles search could help, but pairs/triples etc. search slowed down algorithm, so those methods were not useful in stabilization and acceleration backtracking algorithms.

Serg

[Mathimagics]

Spasiba, Serg

If my specs were for a "normal" puzzle, ie one with a unique solution, then yes I'd expect to find some singles in many cases, and thus speed things up.

But what I am doing above is to ask the question "here is a jigsaw layout, does it have any solutions?". I can't nominate any givens other than a single row, or column, or region set to 1-9. Singles are highly unlikely in such circumstances.

But I have a method in place that works quite well - I run DLX with givens = row 1, row 2 ... with a low iteration limit, until I get a result. In the case quoted above, it solves at row 4 for a total time of 0.013s, which is very acceptable.