For the Harker Research Symposium
Version: 1.2
Date: 2006 April 20
Knuth’s paper on Dancing Links can be found here or follow the credits
links below.
Dr. Donald Knuth’s Dancing Links Algorithm solves an Exact Cover situation. The Exact Cover problem can be extended to a variety of applications that need to fill constraints. Sudoku is one such special case of the Exact Cover problem.
In early 2006, I participated in the ACSL Competition. The prompt of the competition was to create a simple Sudoku solver. I had never solved a Sudoku puzzle so I researched on methods to approach the puzzle. I came across several strategy guides, Sudoku forums, and computer solvers. Hinted amongst the computer programs was the dancing links algorithm. However, given the time and simplicity required for the competition, I reverted to a simple brute force candidate elimination algorithm to solve the simple Sudoku given by the ACSL. However, I found that without a guessing and backtracking algorithm, I could not solve anything beyond the simplest puzzles.
Then around came the Symposium. I was unsure of what the symposium really meant, but with the influence of my CS teacher, Mr. Feinberg, I entered with the notion of research the Dancing Links algorithm and creating a Sudoku solver. In creating the program, I read Knuth’s paper and watched his recorded lecture. Although there are several different versions of programs written in different languages available online with source code, I did not reference them. Rather, I went ahead to discover the intricacies of the algorithm through my own exploration. I also created the simple graphical interface, which displays the data structure uses: the matrix of doubly-linked nodes.
And so, I learned what the Exact Cover problem was, how the algorithm worked to extract the answer from the problem, how the Exact Cover problem can be adapted to Sudoku, and how I could build a program to accomplish my goal to create the Sudoku Solver.
Over the past two months, I have ventured through my first real encounter with Computer Science and discovered its underlying potential and power. With my background in web design, I have gained another facet of admiration for CS.
The rest of the paper will describe the Exact Cover Problem, the Dancing Links Algorithm, and the application to Sudoku.
Given a matrix of 1’s and 0’s the Dancing Links will find a set or more
of rows in which exactly one 1 will appear for each column. For example, in Knuth’s paper
figure 3, a matrix is given as:
0 0 1 0 1 1 0
1 0 0 1 0 0 1
0 1 1 0 0 1 0
1 0 0 1 0 0 0
0 1 0 0 0 0 1
0 0 0 1 1 0 1
Rows 1, 4, 5 are a set that solves this Exact Cover Puzzle.
Knuth takes advantage of a basic principle of doubly-linked lists. When removing an object from a list, only two operations are needed:
x.getRight().setLeft( x.getLeft() )
x.getLeft().setRight( x.getRight() )
However, when putting the object back in the list, all is needed is to do the reverse of the operation.
x.getRight().setLeft( x )
x.getLeft().setRight( x )
All that is needed to put the object back is the object itself, because the object still points to elements within
the list. Unless x’s pointers are changed, this operation is very simple.
Dancing Links takes the Exact Cover matrix and puts it into a toroidal doubly-linked list. For every
column, there is a special ColumnNode, which contains that column’s Unique Name
and the column’s size, the number of nodes in the column. Every 1 in the list,
is a Node. Each Node points to another object up, down, left, right, and to its
corresponding ColumnNode. A special ColumnNode h points to the first ColumnNode
on the left as a starting point for the algorithm. So Knuth’s figure 3 would become:
Given the ColumnNode h, the searching algorithm is then simplified to:
if( h.getRight() == h ) {
printSolution();
return;
}
else {
ColumnNode column = chooseNextColumn();
cover(column);
for( Node row = column.getDown() ; rowNode != column ; rowNode = rowNode.getDown() ) {
solutions.add( rowNode );
for( Node rightNode = row.getRight() ; otherNode != row ; rightNode = rightNode.getRight() )
cover( rightNode );
Search( k+1);
solutions.remove( rowNode );
column = rowNode.getColumn();
for( Node leftNode = rowNode.getLeft() ; leftNode != row ; leftNode = leftNode.getLeft() )
uncover( leftNode );
}
uncover( column );
}
cover( ColumnNode c ) This function is the crux of the algorithm. It removes a column from the
matrix as well as remove all rows in the column from other columns they are in. The code becomes:
Node column = dataNode.getColumn();
column.getRight().setLeft( column.getLeft() );
column.getLeft().setRight( column.getRight() );
for( Node row = column.getDown() ; row != column ; row = row.getDown() )
for( Node rightNode = row.getRight() ; rightNode != row ; rightNode = rightNode.getRight() ) {
rightNode.getUp().setDown( rightNode.getDown() );
rightNode.getDown().setUp( rightNode.getUp() );
}
}
Note that we first remove the column from the other columns. Then we go down a column and remove the row by traversing the row to the right.
Let’s look at some illustrations. Here is the matrix before Column A is covered. All the links in bold are the links that are going to be affected by the cover function.
Now here is the matrix after Column A has been covered. Notice how Column A and rows 2 and 4 are now independently
linked outside of the matrix. In effect, they have been removed. Also note that each node that has
been removed from the matrix still points to an element inside the matrix. This allows us to easily
backtrack.
uncover( ColumnNode c ) This is the answer to easy backtracking. Taking advantage of the fact that
every node that has been removed retains information about its neighbors, we can easily put the
node back into the matrix using the reverse operation of cover.
Node column = dataNode.getColumn();
for( Node row = column.getUp() ; row != column ; row = row.getUp() )
for( Node leftNode = row.getleft() ; leftNode != row ; leftNode = leftNode.getRight() ) {
leftNode.getUp().setDown( leftNode.getDown() );
leftNode.getDown().setUp( leftNode.getUp() );
}
column.getRight().setLeft( column.getLeft() );
column.getLeft().setRight( column.getRight() );
}
Notice that the traversal through the column and row are opposite to that of cover. We first
put the rows back by traveling up the column and to the left of the row. Then we put the column back.
In effect, we undo the operation of cover.
printSolution() takes all the rowNodes in the solution index, which is built by some data structure
solutions and translates their positions in the matrix into the positions in the actual puzzle.
chooseNextColumn() advances the column pointer right or chooses the column with the least number
of nodes. Choosing the column with the least number of nodes decreases the branching of the algorithm. It can
be ignored if this isn’t needed.
A solution is found when all the columns have been removed from the matrix. This means that very row that we have added to the answer has one node in every column. All constraints have been satisfied by the set of rows.
A complete run-through of this algorithm is shown in file: Exact.Cover.Runthrough.xls.
Sudoku is a logic puzzle. On a 9x9 grid with 3x3 regions, the digits 1-9 must be placed in each cell such that every row, column, and region contains only one instance of the digit. Placing the numbers is simply an exercise of logic and patience. Here is an example of a puzzle and its solution:
Images from http://www.nikoli.co.jp/puzzles/1/index_text-e.htm
To create the sparse matrix of Sudoku needed to convert the problem into an Exact Cover Problem, we need to recognize what the rows and columns represent.
The columns represent the constraints of the puzzle. In Sudoku, we have four:
Each number comes with its own set of constraints. Therefore there are SIZE^2 * 4 columns., where
SIZE is the number of candidates/rows/cols there are in the Sudoku Puzzle. In a 4x4, this would be
64 columns. In a 9x9, this would be 324 columns.
The rows represent every single possible position for every number. Therefore, there are SIZE ^ 3
rows. In a 4x4, this would be 64 columns. In a 9x9, this would be 729 rows. Each row would represent only one
candidate position. Therefore, only 4 1s will be in the row, representing the constraints of that position.
The sparse matrix for a 4x4 Sudoku puzzle is seen in: 4x4.dlx.64x64.xls.
The 9x9 sparse matrix is impractical to create by hand.
Given initial positions in the matrix, those rows will be included in the answer and covered. Then
the Search algorithm will produce the solutions to the puzzle.
Having gone through 5 different revisions of the code, I have finally produced a program that can be presented. The following is a list of features of the program.
ColumnNode h. The second minimizes the branching
of the algorithm by looking for the column with the least number of nodes in the column. The second method
is much faster for solving 16x16 Sudoku puzzles. Both methods can be used in this programDancing Links is a powerful algorithm that solves Exact Cover problems. These problems can lead to interesting algorithmic exercises such as the Pentominos problem, polyiamonds, tetrasticks, the N queens, traveling knight, and other chessboard derivatives. However, Exact Cover problems aren’t just theoretical mathematical puzzles though. They describe many real life problems: problems such as making hotel room assignments given a group that has a many specific room requests, and organizing simple flight schedules for airports. Dancing Links is a backtracking, depth-first algorithm that can find all possible solutions of the problem.
© 2006
Document by: Jonathan Chu