Sudoku implementation of DLX in PHP 5 objects

Ruud · Site Admin

The many requests for PHP solver/generator code has prompted me to rewrite some of my core code in PHP and make it available through this forum to the rest of the world.

I have tested this code on PHP 5.1.1 and it works like a charm.

On PHP 4.3.10-16 it does not work. Anyone who can retrofit the code to work with PHP 4 is encouraged to do so and post the modified code below.

There are several trace calls in the code that I have commented out. They have been very useful for debugging purposes, but maybe you want to change something in the code and use them again, so I left them in the code. A few to show the solution were left to show where the good things happen.

The solver is scalable, but I have not tested all settings.

Because this subject is so well documented elsewhere, I have not commented each line, but I did use self documenting names thoughout the code.

The optimizations in the search for the best column have resulted in extended column size administration. The overhead is justified by the speed increase of the main code.

Comments and improvements are appreciated.

lath · Posted: Tue Jul 25, 2006 10:48 pm Post subject:

Wow, thanks a ton! This will prove very useful.

So, correct me if I'm wrong, here's what I need to do:

I already have code that will generate completed puzzles.

1) Randomly remove a cell from the puzzle.
2) Run through $dancer->Solve
2a) If more than one solution, put number back and goto step 1 again.
3) Continue until x desired givens are left.

And I have a sudoku puzzle, right?

If I want to add different levels of difficulty, how can I tell which techniques are required to solve the puzzle?

Thanks.

Ruud · Site Admin

Your process sounds about right.

To add 180 degree symmetry, generate a random number N between 0 and 40, and clear cells N and 80-N,unless N=40.

You need a stop condition. Minimum number of clues is an option. Also create a mask for the clues that you tried to remove. Stop when all clues have been removed or tried.

Normally, difficulty rating is tested afterwards with a solver that uses human-style techniques.

This solver has a property that will show immediately whether the puzzle requires techniques beyond singles.

if ($dancer->Breath == 81) // only singles are required
if ($dancer->Breath > 81) // other techniques needed

There are a few rules of thumb, but you need to confirm this with a human-style solver. Use it as a kind of triage.

81 - Singles only
82-86 - Locked candidates
87-95 - Subsets and fish
96-120 - Multiple techniques
120-250 - + coloring, XY-chains
>250 - all kinds of weird crap

That's about it.

good luck!

humble_programmer · Posted: Thu Feb 01, 2007 3:19 pm Post subject:

Can you elaborate on the purpose and logic of the CoverFromSize() and UncoverFromSize() functions in your PHP example? I'm trying to optimize my C# Dancing Links implementation, and suspect that I can gain some performance by looking harder at which column to choose. (Another "board member" rightly pointed out that the C# code I posted before Christmas is actually using Algorithm X instead of Dancing Links...oh, the shame!)
_________________
Cheers!
Humble Programmer
,,,^..^,,,
www.humble-programmer.com

Ruud · Site Admin

The Sizes array keeps track of the number of remaining columns for each size. (ranging from 0 to 9)

ColSizeIncremented() and ColSizeDecremented() update this array when the column size is changed.

CoverFromSize() is called when a column is covered. Its size does not need to be zero at that point, so the Sizes element for the size of that column is decremented.

UncoverToSize() reverses this operation when the column is uncovered when the program backtracks (or tracks back?)

All 4 methods also process the effects for the BestSize variable. This variable is used in the recursive process to determine when to stop searching the columns. Once a column with size==BestSize is encountered, it is selected, because there will not be any columns with a smaller size.

This optimization works best if you mainly solve difficult puzzles. For easier Sudokus, it is quicker to stop the search after you found a column with size<=1.

Ruud

yAnTar · Posted: Mon Apr 16, 2007 2:20 pm Post subject: Work not up to the end

Work not up to the end

When sudoku is -
901000802002000700400000005640209071080703020000405000000907000710000083004000200
Solution -
901304862832601700406800305640289071080703020000405038308907100710020083064108297

yAnTar · Posted: Wed Apr 18, 2007 2:49 pm Post subject:

Why ?
Is normal ?
I must solve by other methods to end or ... ?

Sorry of my english.

Pat · Posted: Sun Apr 29, 2007 8:02 am Post subject: re: Work not up to the end

Kaimi · Posted: Fri May 25, 2007 8:21 am Post subject:

there is a problem. dlx solver must find full solution if it exists, and in this case it exists. my version found it.
and there is another problem. when solving empty puzzle, solution 3 and 4 are equal. I found it out when tested my own implementation.