other.dancing_links
===================

.. py:module:: other.dancing_links

.. autoapi-nested-parse::

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

.. autoapisummary::

   other.dancing_links.ColumnNode
   other.dancing_links.DLXNode
   other.dancing_links.DancingLinks


Module Contents
---------------

.. py:class:: ColumnNode(name: str)

   Bases: :py:obj:`DLXNode`


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


   .. py:attribute:: name


   .. py:attribute:: size
      :value: 0



.. py:class:: DLXNode

   Represents a node in the Dancing Links structure.


   .. py:attribute:: column
      :value: None



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

   Dancing Links structure for solving the Exact Cover problem.


   .. py:method:: _choose_column() -> ColumnNode

      Select the column with the smallest size (heuristic).



   .. py:method:: _cover(col: ColumnNode) -> None

      Covers a column (removes it from the matrix).



   .. py:method:: _search() -> None

      Recursive Algorithm X search.



   .. py:method:: _uncover(col: ColumnNode)

      Uncovers a column (reverses _cover).



   .. py:method:: solve() -> list

      Find all exact cover solutions.



   .. py:attribute:: columns


   .. py:attribute:: header


   .. py:attribute:: solution
      :value: []



   .. py:attribute:: solutions
      :value: []