This module provides an implementation of the “dancing links” algorhthm to solve the “exact cover” problem.
The “exact cover” problem:

Given a set of vectors containing 0's and 1's:

Find a subset of these vectors that collectively contain one and only one 1 in each and every column.
For example the follwing set of vectors:

A = [ 0, 1, 0]

B = [ 1, 1, 0]

C = [ 1, 0, 0]

D = [ 0, 0, 1]
Has two solutions:

A = [ 0, 1, 0]

C = [ 1, 0, 0]

D = [ 0, 0, 1]
and

B = [ 1, 1, 0]

D = [ 0, 0, 1]
A better description of the problem can be found here: en.wikipedia.org/wiki/Exact_cover
The “dancing links” algorithm is a commonly used solution for this problem and was found by Donald Knuth. The algorithm involves the construction of a sparse matrix containing nodes that are doublylinked both horizontally and vertically. The matrix itself simply facilitates the depthfirst search (aka backtracking) part of the algorithm.
The importance of the doublylinked nodes are that they allow for quick removal/restoration of rows/columns of nodes, which is exactly what a backtracking algorithm for the “exact cover” problem needs.
horizontal removal:

node.left.right = node.right

node.right.left = node.left
horizontal restoration:

node.left.right = node

node.right.left = node
A better description of the algorithm can be found here: en.wikipedia.org/wiki/Dancing_Links