Using DLX for base/cover set logic eliminations

PIsaacson · Last edited by PIsaacson on Sat May 09, 2009 9:11 am; edited 2 times in total

Rather than using Knuth's Dancing Links (DLX) implementation of his Algorithm X to competely solve a sudoku puzzle, I am instead going to discuss how to use DLX to generate all possible covers sets for a given base set.

Some preliminary requirements:

1) Download libexact and read the PDF manual. http://www.cs.helsinki.fi/u/pkaski/libexact/libexact-1.0.tar.gz
2) Read Allan Barker's brief introduction to set/link-set logic. http://sudokuone.com/sweb/guide.htm
3) Basic knowledge of C/C++ and STL is important, but not necessarily critical.

The base/cover algorithm requires some outside method to discover/generate a base set. Currently, I'm using doubly-linked ALSs to generate a vector describing all the cells of both ALSs, but you can use whatever technique you want to generate such lists. However, the following code only works well for rank-0 logical structures, so if you want rank-1 chains etc, you'll have to adjust the filter to allow base+1 sized solutions, modify the elimination code to correctly test the overlap counts, and probably switch from cell base sets to lists of the actual sets used to link candidates.

Basically the technique works like this:

1) Find any interesting set of cells to examine. This becomes the base set.
2) Setup the DLX problem using the libexact (modified) API.
3) Execute libexact exact_solve to find all valid combinations of rows/cols/boxes that exactly cover the base cells.
4) For each solution, any outside candidate contained in a cover set but not in a base set can be eliminated.

This is similar to fishing algorithms that use base/cover sets for single digit analysis. In fact, I adapted it from my experimental fishing engine that also uses DLX in this manner. Here, it is being used in a more general fashion.

So, on to the code (written in C++ and depending heavily on STL):

PIsaacson · Posted: Thu May 07, 2009 8:27 am Post subject:

Updated build files for my testbed ALS engine:

Makefile.txt needs to be renamed to Makefile and all the others need to be placed in the same directory for correct building. I'm now using the mingw compilers under cygwin, so this should build correctly on just mingw.

http://pisaacson.fileave.com/Bernhard/Makefile.txt
http://pisaacson.fileave.com/Bernhard/combination.h
http://pisaacson.fileave.com/Bernhard/exact.h
http://pisaacson.fileave.com/Bernhard/sudoku.h
http://pisaacson.fileave.com/Bernhard/exact.cpp
http://pisaacson.fileave.com/Bernhard/sudoku.cpp

Pre-built library and executable

http://pisaacson.fileave.com/Bernhard/libexact.a
http://pisaacson.fileave.com/Bernhard/sudoku.exe

You should re-make the executable if you have the correct cygwin/mingw environment, then test using:

sudoku -bvgw -Xprsak -A9 -B0 -K2 -T-1 royle17.txt royle17.sud > royle17.log

This assumes you have downloaded the new 48010 royle17 collection into the current working directory from http://people.csse.uwa.edu.au/gordon/sudoku17
The command will run the ALS engine and locate all doubly-linked ALSs and Death Blossoms and generate an Xsudo collection in royle17.sud with the output logged in royle17.log

If all goes well, you should match (use "tail -16 royle17.log") the following statistics for the updates/call and % eff. The others depend upon the speed of the processor, but should be similar if normalized.

PIsaacson · Posted: Thu May 07, 2009 8:28 am Post subject:

For those who may have generate the above royle17.sud file and attempted to directly load it into Xsudo, it won't work because there are 62561 cases in one file. To circumvent this and to match Allan's new 2000 case limit, I have a small program that reads large sud collections, sorts them based on the keys that I have internally stored in the collection (see write_xsudo), then breaks them up into multiple 2000 max chunks.

Download: http://pisaacson.fileave.com/Bernhard/sortsud.cpp

Place it in the same directory as the other files and compile with:
g++ -O -I. sortsud.cpp -o sortsud

Execute as sortsud <filename> as in:
sortsud royle17.sud

Again, if you've been following along, this will generate 32 output files with the following output:

PIsaacson · Posted: Thu May 07, 2009 9:02 am Post subject:

Setting up a cygwin environment - read the installation instructions from http://cygwin.com/

I'm running the beta 1.7 cygwin install from http://cygwin.com/setup-1.7.exe

You'll need to manually select the following packages:

PIsaacson · Posted: Thu May 07, 2009 9:29 am Post subject:

The above posting were originally posted on http://www.sudoku.com/boards/viewtopic.php?t=6694

There was no response/interest on the Players Forum, so perhaps I should have posted here first? Regardless, there are many discussions on the Players Forum that include various base/cover diagrams. So for the highly self-motivated individuals, I recommend studying any (if not all) of Allan Barker's postings. It's the implementation of his theory that I'd like to explore from a design/coding POV.

Cheers,
Paul

PIsaacson · Posted: Fri May 08, 2009 8:56 pm Post subject:

I feel compelled to issue this disclaimer: My ALS engine is not intended to be used as a solver.

It is a testbed for locating various types of ALS chains and Death Blossoms and investigating the associated base/cover logic. Solving a puzzle to completion, while interesting and often possible, is not its main mission. The included techniques are present to bring puzzles to a known quasi-SSTS condition for large collections and/or puzzles not otherwise presented as PM grids after SSTS. With that proviso having been disclosed, it is still extraordinary how powerful ALS/DB can be in terms of solving puzzles without resorting to other higher level techniques.

PIsaacson · Posted: Wed May 13, 2009 8:12 pm Post subject:

nukefusion · Posted: Tue Aug 11, 2009 9:50 am Post subject:

Hi Paul,

It appears I'm rather late stumbling over this thread. Thanks for posting this stuff up as I'm currently looking at Death Blossoms myself. I've found that discovering the ALS's and matching up potential stems is easy, but the slow part comes when testing the various combinations of stem cell/petals to see which are valid (i.e. no overlapping cells between ALS's) and which produce any useful eliminations.

I think I'm going to have to re-read your posts a few times in order to gain even a small understanding of how it all fits together but it certainly looks very interesting!

PIsaacson · Posted: Tue Aug 11, 2009 7:08 pm Post subject:

Matt,

I have the ALS and DB engine in a somewhat simpler form in pascal at http://pisaacson.fileave.com/Sudoku/sudoku.zip

There has been no activity/response for this thread (other than yours!), so I have not kept the code current with my latest implementation of base/cover logic ala Allan Barker's SLG theory. If you are just interested in ALSs and DBs, then the base/cover logic is probably overkill anyway and the pascal version is more up-to-date with my full solver.

Cheers,
Paul