other.dancing_links

Implementation of the Dancing Links algorithm (Algorithm X) by Donald Knuth. https://en.wikipedia.org/wiki/Knuth’s_Algorithm_X https://en.wikipedia.org/wiki/Dancing_links

>>> universe = [1, 2, 3, 4, 5, 6, 7]
>>> subsets = [
...     [1, 4, 7],
...     [1, 4],
...     [4, 5, 7],
...     [3, 5, 6],
...     [2, 3, 6, 7],
... ]
>>> dlx = DancingLinks(universe, subsets)
>>> sols = dlx.solve()
>>> len(sols) == 0
True

Classes

ColumnNode	Represents a column header node, keeping track of its column size.
DLXNode	Represents a node in the Dancing Links structure.
DancingLinks	Dancing Links structure for solving the Exact Cover problem.

Module Contents

class other.dancing_links.ColumnNode(name: str)

Bases: DLXNode

Represents a column header node, keeping track of its column size.

name

size = 0

class other.dancing_links.DLXNode

Represents a node in the Dancing Links structure.

column = None

class other.dancing_links.DancingLinks(universe: list[int], subsets: list[list[int]])

Dancing Links structure for solving the Exact Cover problem.

_choose_column() → ColumnNode

Select the column with the smallest size (heuristic).

_cover(col: ColumnNode) → None

Covers a column (removes it from the matrix).

_search() → None

Recursive Algorithm X search.

_uncover(col: ColumnNode)

Uncovers a column (reverses _cover).

solve() → list

Find all exact cover solutions.

columns

header

solution = []

solutions = []