Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Exact Cover Problem via Dancing Links """ # dlx.py # Copyright (c) 2006,2008 Antti Ajanki <antti.ajanki@iki.fi>
# Heavily Modified Feb 2008, Tom Boothby # * Added a function which takes a Sage matrix and solves # the exact cover problem for it. # * Recursive search is now iterative # * Removed callback functionality # * Revamped the class to be a pythonic generator; new usage: # for cover in DLXMatrix(ones,initialsolution): # blah(cover) # * DOCUMENTATION AND TESTS GALORE HOLYCRAP 100% COVERAGE!!!!!1!!111@%^%*QQ!@E~
# DLXMatrix class is used to store and solve an exact cover problem # with help of Dancing Links [1] technique by Donald Knuth. The # problem can be stated as an attempt to leave out rows of a 0/1 # matrix until remaining matrix has exactly one 1 in each column. # Knuth proposes a fast solution technique based on clever trick with # double linked list. # # This implementation will return row numbers of the solution instead # column indexes (like in the Knuth's paper). # # [1] Donald E Knuth, Dancing links, preprint, available at # http://www-cs-faculty.stanford.edu/~knuth/preprints.html
# This program is free software; you can redistribute it and/or # modify it under the terms of the GNU General Public License # as published by the Free Software Foundation; either version 2 # of the License, or (at your option) any later version.
ROOTNODE = 0
# Node's attributes # LEFT, RIGHT, UP and DOWN are identifiers of corresponding neighbors # INDEX is the (row) index of the node (None in the header nodes) # COLUMN/COUNT is column index on a regular node and count of nodes on # a header node LEFT = 0 RIGHT = 1 UP = 2 DOWN = 3 COLUMN = 4 INDEX = 5 COUNT = 5
class DLXMatrix: def __init__(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
EXAMPLES::
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. """
def __eq__(self, other): r""" Return ``True`` if every attribute of ``other`` matches the attribute of ``self``.
INPUT:
- ``other`` - a DLX matrix
EXAMPLES::
sage: from sage.combinat.dlx import * sage: M = DLXMatrix([[1,[1]]]) sage: M == loads(dumps(M)) True """ return False
def __iter__(self): """ Returns self.
TESTS::
sage: from sage.combinat.dlx import * sage: M = DLXMatrix([[1,[1]]]) sage: M.__iter__() is M True """
def _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: count 0 """
def _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: fullcount 6 """ initialsolution = [] # LEFT, RIGHT, UP, DOWN, COLUMN, INDEX/COUNT
# optimization: local variables are faster
# Do we need more headers?
# Add new nodes to indexes newind..newind+len(columns)-1 # LEFT and RIGHT links can be calculated when created the # node, only UP, DOWN and COUNT have to be updated when # adding new nodes
# Remove columns that are required to be in the solution self._covercolumn(nodetable[j][COLUMN])
def _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: M._nodes[three][RIGHT] == ROOTNODE True sage: M._nodes[two][COUNT] 1 sage: M._nodes[three][COUNT] 0 """
def _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: M._nodes[two][LEFT] == one True sage: M._nodes[two][COUNT] 2 """
def __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 = next(M) ....: 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] """
else: else: else:
next = __next__
def 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)] """
def 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: OneExactCover(M) [(1, 1, 0), (0, 0, 1)] """
|