Package sage :: Package combinat :: Module dlx

Module dlx


Exact Cover Problem via Dancing Links

Classes

[hide private]

DLXMatrix

Functions

[hide private]

AllExactCovers(M)
Utilizes A.

source code

OneExactCover(M)
Utilizes A.

source code

Variables

[hide private]

ROOTNODE = 0

LEFT = 0

RIGHT = 1

UP = 2

DOWN = 3

COLUMN = 4

INDEX = 5

COUNT = 5

Function Details

[hide private]

AllExactCovers(M)

source code


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

OneExactCover(M)

source code


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