Introduction
This is a VB.NET library with all the necessary classes for exact cover problem solving with Dancing Links. The demo project shows how to use the library for solving Sudoku.
Background
Two years ago, I started solving Sudoku which is still one of my favorites for spending free time. When searching the internet for tasks, I found the top 95 Sudokus. There were no solutions given, and when trying to solve them, I often figured out I made a mistake in some earlier stage of solving. To verify part solutions, I needed the solutions and couldn't find a solver at that time.
When searching for methods for solving, I found Knuth's Dancing links algorithm. I had problems transferring Knuth algorithms to objects till I found Stan Chesnutt's Java implementation of this algorithm. Converting Java code to VB was easy. At first, the program didn't work, but after consulting Knuth's paper and making some adjustments, I managed to work it out.
At the beginning, the solving time varied very much from task to task, in some cases, to an unacceptable two minutes. When I changed the order of the selection of the columns so that the columns with the smallest number of rows are handled first, I managed to solve in times less than a second for any task I tried. Actually such a columns selection is advised by Knuth, except when a previous ordering of columns is done to speed up solving.
Though the Dancing Links library is more or less converted from Java, it has been improved, extended, and works, proven with the demo program. I used Chesnutt's naming, which I find very convenient.
Using the code
The library consists of three classes:
DancingNodeDancingColumnDancingArena
Classes for solving the actual problems must extend the DancingArena class. The user should only write the class constructor and the HandleSolution procedure. The SudokuArena class is an example of such an extension. The demo project shows how to use the SudokuArena class. You can open a Sudoku saved in an XML or text file and solve it. The program show the number of solutions and the first valid solution.
The library allows some useful settings. We can set whether all solutions, or only the first solution, or no solution (in case we want to know the number of solutions) should be saved. I have provided some Sudoku tasks (4.1 KB) in different formats to play with.
The DancingArena class is extended with the constructor, enabling the use of secondary columns to enable use in solving problems like 8 queens. The class QueenArena shows how to solve the 8 queens problem with Dancing Links.
Points of interest
I'm using The Dancing Link library in my project "Yet another Sudoku solver". It proves useful for fast verification of if there exists one and only one solution.
There are many formats for Sudoku task presentation, and many of them don't provide non-square task representations. For a long time, I've been using XML for storing data, so I decided to make a specification (76 KB) to store Sudoku tasks and solutions in an XML file. In my demo project, the specification and schema definition are included. I would like to make this specification public, and if there are interested parties, I would be happy to continue the specification project with them.
History
