Module dlxcpp

Solves the Exact Cover problem by using the Dancing Links
algorithm described by Knuth.

Consider a matrix M with entries of 0 and 1, and compute a 
subset of the rows of this matrix which sum to the vector
of all 1's.

The dancing links algorithm works particularly well for 
sparse matrices, so the input is a list of lists of the
form:
    [
     [i_11,i_12,...,i_1r]
     ...
     [i_m1,i_m2,...,i_ms]
    ]
where M[j][i_jk] = 1. 

The first example below corresponds to the matrix

    1110
    1010
    0100
    0001

which is exactly covered by

    1110
    0001

and

    1010
    0100
    0001

If soln is a solution given by DLXCPP(rows) then

[ rows[soln[0]], 
  rows[soln[1]], 
  ...
  rows[soln[len(soln)-1]]
]

is an exact cover.

Solutions are given as a list 

EXAMPLES:
    sage: rows = [[0,1,2]]
    sage: rows+= [[0,2]]
    sage: rows+= [[1]]
    sage: rows+= [[3]]
    sage: print [ x for x in DLXCPP(rows) ]
    [[3, 0], [3, 1, 2]]

Solves the exact cover problem on the matrix M (treated 
as a dense binary matrix).

EXAMPLES:
    No exact covers:

    sage: M = Matrix([[1,1,0],[1,0,1],[0,1,1]])
    sage: print [cover for cover in AllExactCovers(M)]
    []

    Two exact covers:

    sage: M = Matrix([[1,1,0],[1,0,1],[0,0,1],[0,1,0]])
    sage: print [cover for cover in AllExactCovers(M)]
    [[(1, 1, 0), (0, 0, 1)], [(1, 0, 1), (0, 1, 0)]]

Solves the exact cover problem on the matrix M (treated 
as a dense binary matrix).

EXAMPLES:
    sage: M = Matrix([[1,1,0],[1,0,1],[0,1,1]])  #no exact covers
    sage: print OneExactCover(M)
    None
    sage: M = Matrix([[1,1,0],[1,0,1],[0,0,1],[0,1,0]]) #two exact covers
    sage: print OneExactCover(M)
    [(1, 1, 0), (0, 0, 1)]