A Java Sudoku Solver using Knuth's Dancing Links Method

Sudoku in Java, using Knuth's Dancing Links method

Donald Knuth's "Dancing Links" paper (available from his preprints page) describes an algorithm for simplifying sparse matrices to a non-reducible state. The paper describes applications of this method to pentominoes, eight-queens, and certain word puzzles. Knuth calls his method "DLX", and it is commonly called "Dancing Links". The method can be easily applied to the popular Sudoku puzzles. I have written a simple Dancing Links library and a Sudoku front-end. This is experimental code lacking a polished user interface.

Knuth's DLX algorithm is naturally implemented using recursion. However, recursive implementations do not neatly fit into GUI-based applications written in Java, so an iterative method is used here.

My implementation is in Java, and I've included fairly extensive unit-tests of the core Dancing Links implementation. To use the solver, you will need a Java compiler and run-time environment that can handle the "assert" operations specified in J2SE version 1.4 and later.

Some folks have emailed, asking about copyright or reuse of this implementation. Yes, the actual coding is copyrighted by me, but the real intellectual effort was done by Dr. Knuth, and my contribution was to write the Java code that corresponds to his thoughts. As for reuse, I think it is great if this code gets incorporated into your own projects (commercial or otherwise). I do request that you mention my name in the "about" box or the credits page, or wherever you list the contributors to the project. And, I hope you'll also give credit to Dr. Knuth!

A jar file containing the source code can be found here. Unpack and compile in the usual way, then use "java Sudoku" to solve some sample puzzles which are present in the Sudoku.java source file. You can edit this file to attempt the solution of other Sudoku puzzles, or to extend the solver in various ways.

Of course, I'll add a better user interface. Just as soon as I refresh my Swing skills :-)

Here is a quick outline of the source code files:

Node.java: Implementation of the core object which populates the sparse matrix. The main elements of this object are the right, left, up, and down references. This class is subclassed by ColumnNode.

ColumnNode.java: A subclass of Node, this class indicates the header for each column in the sparse matrix.

DancingLinksArena.java: A utility class which ties together the Node and ColumnNode classes into an implementation of the DancingLinks algorithm. The methods that manipulate the sparse matrix are in this class.

dlinks.java: A utility class that does unit-tests of the Node, ColumnNode, and DancingLinksArena classes. The main() method is invoked from the command-line to verify basic functionality of the Dancing Links implementation.

DancingLinksSudoku.java: A bridge class which melds the requirements of Sudoku with the Dancing Links algorithm.

Sudoku.java: The Sudoku client implementation, containing the puzzle data. This is the application-level implementation -- the other classes are scaffolding or the Dancing Links implementation.

I've also used the Dancing Links implementation in a pentominoes solver.

questions, comments, etc to chesnutt at gmail dot com

return to Stan Chesnutt's webpage

$Header: /home/cvs/htdocs/stan/sudoku.html,v 1.9 2006/06/11 04:06:33 chesnutt Exp $