Exact Cover Problem via Dancing Links

sage.combinat.dlx.AllExactCovers(M)

Utilizes A. Ajanki’s DLXMatrix class to solve 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: 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)]

class sage.combinat.dlx.DLXMatrix(ones, initialsolution=None)

next()

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]

sage.combinat.dlx.OneExactCover(M)

Utilizes A. Ajanki’s DLXMatrix class to solve 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)]