18.10 Exact Cover Problem via Dancing Links

Module: sage.combinat.dlx

Exact Cover Problem via Dancing Links

Module-level Functions

AllExactCovers( M)

Utilizes A. Ajanki's DLXMatrix class to solve the exact cover problem on the matrix M (treated as a dense binary matrix).

sage: M = Matrix([[1,1,0],[1,0,1],[0,1,1]])  #no exact covers
sage: for cover in AllExactCovers(M):
...       print cover
sage: M = Matrix([[1,1,0],[1,0,1],[0,0,1],[0,1,0]]) #two exact covers
sage: for cover in AllExactCovers(M):
...       print cover
[(1, 1, 0), (0, 0, 1)]
[(1, 0, 1), (0, 1, 0)]

OneExactCover( M)

Utilizes A. Ajanki's DLXMatrix class to solve the exact cover problem on the matrix M (treated as a dense binary matrix).

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)]

Class: DLXMatrix

class DLXMatrix
DLXMatrix( self, ones, [initialsolution=None])

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: (note the 1-index!) [ [1, [i_11,i_12,...,i_1r]] ... [m, [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

sage: from sage.combinat.dlx import *
sage: ones = [[1,[1,2,3]]]
sage: ones+= [[2,[1,3]]]
sage: ones+= [[3,[2]]]
sage: ones+= [[4,[4]]]
sage: DLXM = DLXMatrix(ones,[4])
sage: for C in DLXM:
...      print C
[4, 1]
[4, 2, 3]

NOTE: The 0 entry is reserved internally for headers in the sparse representation, so rows and columns begin their indexing with 1. Apologies for any heartache this causes. Blame the original author, or fix it yourself.

Functions: next

next( self)

Search for the first solution we can find, and return it.

Knuth describes the Dancing Links algorithm recursively, though actually implementing it as a recursive algorithm is permissible only for highly restricted problems. (for example, the original author implemented this for Sudoku, and it works beautifully there)

What follows is an iterative description of DLX:

stack <- [(NULL)] level <- 0 while level >= 0: cur <- stack[level] if cur = NULL: if R[h] = h: level <- level - 1 yield solution else: cover(best_column) stack[level] = best_column else if D[cur] != C[cur]: if cur != C[cur]: delete solution[level] for j in L[cur], L[L[cur]], ... , while j != cur: uncover(C[j]) cur <- D[cur] solution[level] <- cur stack[level] <- cur for j in R[cur], R[R[cur]], ... , while j != cur: cover(C[j]) level <- level + 1 stack[level] <- (NULL) else: if C[cur] != cur: delete solution[level] for j in L[cur], L[L[cur]], ... , while j != cur: uncover(C[j]) uncover(cur) level <- level - 1

TESTS:

sage: from sage.combinat.dlx import *
sage: M = DLXMatrix([[1,[1,2]],[2,[2,3]],[3,[1,3]]])
sage: while 1:
...     try:
...         C = M.next()
...     except StopIteration:
...         print "StopIteration"
...         break
...     print C
StopIteration
sage: M = DLXMatrix([[1,[1,2]],[2,[2,3]],[3,[3]]])
sage: for C in M:
...       print C
[1, 3]
sage: M = DLXMatrix([[1,[1]],[2,[2,3]],[3,[2]],[4,[3]]])
sage: for C in M:
...       print C
[1, 2]
[1, 3, 4]

Special Functions: __eq__,$ \,$ __init__,$ \,$ __iter__,$ \,$ _constructmatrix,$ \,$ _covercolumn,$ \,$ _uncovercolumn,$ \,$ _walknodes

__eq__( self, other)

Return True if every attribute of other matches the attribute of self.

Input:

other
- a DLX matrix

sage: from sage.combinat.dlx import *
sage: M = DLXMatrix([[1,[1]]])
sage: M == loads(dumps(M))
True

__iter__( self)

Returns self.

TESTS:

sage: from sage.combinat.dlx import *
sage: M = DLXMatrix([[1,[1]]])
sage: print M.__iter__() is M
True

_constructmatrix( self, ones, [initialsolution=None])

Construct the (sparse) DLX matrix based on list 'ones'. The first component in the list elements is row index (which will be returned by solve) and the second component is list of column indexes of ones in given row.

'initialsolution' is list of row indexes that are required to be part of the solution. They will be removed from the matrix.

Note: rows and cols are 1-indexed - the zero index is reserved for the root node and column heads.

TESTS:

sage: from sage.combinat.dlx import *
sage: ones = [[1,[1,2,3]]]
sage: ones+= [[2,[1,3]]]
sage: ones+= [[3,[2]]]
sage: ones+= [[4,[4]]]
sage: DLX = DLXMatrix([[1,[1]]])
sage: DLX._constructmatrix(ones,[4])
sage: c = DLX._nodes[ROOTNODE][RIGHT]
sage: fullcount = 0
sage: while c != ROOTNODE:
...       fullcount += DLX._nodes[c][COUNT]
...       d = DLX._nodes[c][DOWN]
...       while d != c:
...           bad = DLX._nodes[DLX._nodes[d][DOWN]][UP] != d
...           bad|= DLX._nodes[DLX._nodes[d][UP]][DOWN] != d
...           bad|= DLX._nodes[DLX._nodes[d][LEFT]][RIGHT] != d
...           bad|= DLX._nodes[DLX._nodes[d][RIGHT]][LEFT] != d
...           if bad:
...               raise RuntimeError, "Linked list inconsistent."
...           d = DLX._nodes[d][DOWN]
...       c = DLX._nodes[c][RIGHT]
sage: print fullcount
6

_covercolumn( self, c)

Performs the column covering operation, as described by Knuth's pseudocode: cover(c): i <- D[c] while i != c: j <- R[i] while j != i D[U[j]] <- D[j] U[D[j]] <- U[j] N[C[j]] <- N[C[j]] - 1 j <- R[j] i <- D[i]

This is undone by the uncover operation.

TESTS:

sage: from sage.combinat.dlx import *
sage: M = DLXMatrix([[1,[1,3]],[2,[1,2]],[3,[2]]])
sage: one = M._nodes[ROOTNODE][RIGHT]
sage: M._covercolumn(one)
sage: two = M._nodes[ROOTNODE][RIGHT]
sage: three = M._nodes[two][RIGHT]
sage: print M._nodes[three][RIGHT] == ROOTNODE
True
sage: print M._nodes[two][COUNT]
1
sage: print M._nodes[three][COUNT]
0

_uncovercolumn( self, c)

Performs the column uncovering operation, as described by Knuth's pseudocode: uncover(c): i <- U[c] while i != c: j <- L[i] while j != i U[j] <- U[D[j]] D[j] <- D[U[j]] N[C[j]] <- N[C[j]] + 1 j <- L[j] i <- U[i]

This undoes by the cover operation since everything is done in the reverse order.

TESTS:

sage: from sage.combinat.dlx import *
sage: M = DLXMatrix([[1,[1,3]],[2,[1,2]],[3,[2]]])
sage: one = M._nodes[ROOTNODE][RIGHT]
sage: M._covercolumn(one)
sage: two = M._nodes[ROOTNODE][RIGHT]
sage: M._uncovercolumn(one)
sage: print M._nodes[two][LEFT] == one
True
sage: print M._nodes[two][COUNT]
2

_walknodes( self, firstnode, direction)

Generator for iterating over all nodes in given direction (not including firstnode).

TESTS:

sage: from sage.combinat.dlx import *
sage: ones = [[1,[1,2,3]]]
sage: ones+= [[2,[1,3]]]
sage: ones+= [[3,[2]]]
sage: ones+= [[4,[4]]]
sage: DLX = DLXMatrix(ones,[4])
sage: count = 0
sage: for c in DLX._walknodes(ROOTNODE,RIGHT):
...       count += DLX._nodes[c][COUNT]
...       for d in DLX._walknodes(c,DOWN):
...           count -= 1
sage: print count
0

See About this document... for information on suggesting changes.