Click here to Skip to main content
Click here to Skip to main content

Dancing Links Library

, 17 Jul 2007 CPOL
Rate this:
Please Sign up or sign in to vote.
A VB.NET library with all necessary classes for exact cover solving with dancing links.

Screenshot - Dancing_Links_Sudoku_Solver.jpg

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:

  • DancingNode
  • DancingColumn
  • DancingArena

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

  • 2007-07-04: Version 1.0.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Miran.Uhan
Engineer
Slovenia Slovenia
No Biography provided

Comments and Discussions

 
GeneralMy vote of 5 Pinmembermanoj kumar choubey23-Feb-12 22:24 
GeneralMy vote of 1 PinmemberAlexey Prosyankin20-Aug-09 6:42 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141223.1 | Last Updated 17 Jul 2007
Article Copyright 2007 by Miran.Uhan
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid