Implementing the Dancing Links Algorithm in Python

In this notebook, I will implement the Dancing Links algorithm from Donald Knuth's paper called Dancing Links.

The Dancing links algorithm is a very fast algorithm for solving Exact Cover Problems. Examples of these types of problems are Sudoku puzzles, and the N Queens problem.

Exact Cover Problem

What exactly is an Exact Cover Problem? This excerpt from GeeksForGeeks is an excellent description.

Given a collection S of subsets of set X, an exact cover is the subset S* of S such that each element of X is contained is exactly one subset of S*. It should satisfy following two conditions –

The Intersection of any two subsets in S* should be empty. That is, each element of X should be contained in at most one subset of S*

Union of all subsets in S* is X. That means union should contain all the elements in set X. So we can say that S* covers X.

Example (standard representation) –

Let S = { A, B, C, D, E, F } and X = {1, 2, 3, 4, 5, 6, 7} such that –

A = {1, 4, 7}

B = {1, 4}

C = {4, 5, 7}

D = {3, 5, 6}

E = {2, 3, 6 7}

F = {2, 7}

Then S* = {B, D, F} is an exact cover, because each element in X is contained exactly once in subsets {B, D, F} . If we union subsets then we will get all the elements of X –

$B \bigcup D \bigcup F = \{ 1,2,3,4,5,6,7\}$

The Exact cover problem is a decision problem to determine if exact cover exists or not. It is considered to be NP-Complete problem.

The problem can be represented in the form of a matrix where the row represents the subsets of S and columns represent the element of X. The above problem can be represented as –

In the context of matrix representation, our exact cover is the selection of rows such that each column contains only single 1 among selected rows. So we can see below that each column have only single 1 among selected rows B, D, F.

Source: https://www.geeksforgeeks.org/exact-cover-problem-algorithm-x-set-1/

Algorithm X

In the Dancing Links paper, Donald Knuth outlined a solving algorithm that he named Algorithm X shown below.

If A is empty, the problem is solved; terminate successfully.
Otherwise choose a column, c (deterministically).
Choose a row, r, such that A[r, c] = 1 (nondeterministically).
Include r in the partial solution.
For each j such that A[r, j] = 1,
    delete column j from matrix A;
       for each i such that A[i, j] = 1,
            delete row i from matrix A.
Repeat this algorithm recursively on the reduced matrix A.

Source: Dancing Links - Donald E. Knuth, Stanford University

The paper then goes on to describe an implementation of Algorithm X utilizing doubly linked circular lists to implement a sparse matrix. The use of the doubly linked lists allows for quick removal and restoral of columns and rows in the matrix. Donald Knuth named this implementation Dancing Links or DLX for short.