algoxtools 0.1.4

A Fast Algorithm X implementation in Python using Numpy and Numba

algoxtools

A practical implementation of Donald Knuth's Algorithm X in Python using Numpy and Numba.

Open sourced implementations of Algorithm X in Python are plentiful.
Justification of creating algoxtools is that although existing packages are compact and elegantly coded in object oriented Python, a drawback is that for more complex exact cover problems processing the Python interpreted node objects used in the NP-complete algorithm becomes slow. Since use of classes has a poor relation with compilers such as Numba, resulting speed gains are discouraging.

In algoxtools the web of Knuth's Dancing Links nodes is embedded in a numpy array. Since numpy arrays are heterogenous by design and boast high performance libraries, algoxtools aims to come more close to machine level, resulting in performance gain.
The array space used by algoxtools is in 3d, arranged in rows, columns, the third dimension being used for substitutes of class attributes such as pointers and index values. Headers for rows and columns as well as meta data such as current row, column, level and solution at hand are all embedded in the array as well, making the variables as easy to pass as a conventional object.
Algoxtools facilitates unlinking and relinking of rows and columns at once by eleborate indexing which avoids handling each individual node chain*.
Moreover the indexing used shakes off the need for recursion, which allows for returns to caller level from one function.
The array organisation is sparse and uses 16 bit ints. If needed, int size can be easily adapted.
Dynamic allocation of nodes could further optimize use of memory and squeeze out a bit of performance gain, but remains to be implemented.

Installation

pip install algoxtools

Api example

Data taken from Wikipedia

import algoxtools as axt
import numpy as np
INDEX, META, SOLUTIONCOUNT, VALUE, SOLUTION = 0, -1, 0, -1, 1
array = axt.init( 6, 7 )
dt = np.int16
# Rows and cols start from 1!
axt.annex_row( array, 1, np.array([ 1, 4, 7 ], dt ) )
axt.annex_row( array, 2, np.array([ 1, 4 ], dt ) )
axt.annex_row( array, 3, np.array([ 4, 5, 7 ], dt ) )
axt.annex_row( array, 4, np.array([ 3, 5, 6 ], dt ) )
axt.annex_row( array, 5, np.array([ 2, 3, 6, 7 ], dt ) )
axt.annex_row( array, 6, np.array([ 2, 7 ], dt ) )
ii = array[ INDEX, INDEX ]
print( 'Solution:' )
while axt.exact_cover( array ):
    print( array[ META, SOLUTION : ii[VALUE], VALUE ] )

Solution:
[2 4 6]

Above examples is enclosed in jupyter notebook format in the examples folder

Quick api reference guide:

array = init( rows, columns )

Initializes algoxtools array.
Internally the number of columns is one higher than the given value and is used for indexing.
The internal number of rows is two higher than the given value and is used for indexing and storing meta data
Rows and columns numbers cannot exceed the np.int16 maximum value - 1 (+32,766)

Example:

import algoxtools as axt
array = axt.init( 6, 7 )

annex_row( array, row_number, numpy.array( column 1, column 2, .. column n , numpy.int16) )

Assigns linked nodes to the specified columns in a specific row.
row and col values should be higher than 1 and cannot exceed numpy.int16 maximum value - 1
In order to solve an exact cover, all rows must contain at least one column.

Example:

axt.annex_row( array, 4, np.array([ 3, 5, 6 ], np.int16 ) )

bool exact_cover( array )

This is the main function to flip through exact cover solutions, it returns a boolean True if reached an exact cover and returns a boolean False if finished.

Example:

while axt.exact_cover( array )
    print(print( array[ META, SOLUTION : array[ 0,0,-1 ], VALUE ] )

Miscellaneous functions used internally

bool isempty( array )

Returns boolean True if an exact cover is reached else returns a False

Example:

if axt.isempty( array ):
    ## Exact cover found
    level = array[ 0, 0, -1 ]
    print( array[ -1, 1:level, -1 ]

bool mcr_cover( array )

Minimum column rows cover (Or Most-constrained column rows cover) is a composite of internal min_col() and cover() functions.
Initialy it selects the first column with the least number of nodes and the first row in that column and covers all nodes which are orthogonally linked to that entry.
In subsequent calls mcr_cover selects a next row and covers it until all rows are depleted.
Returns a boolean False if no more rows are available, else returns True
This function should be balanced by uncover

Example:

while axt.mcr_cover( array ):
    # Recurse
    search( array )
    axt.uncover( array )

void uncover( array )

Uncover the nodes previously linked to current row and colum entry in the array (selected by mcr_cover)

Internal organisation of algoxtools array:

0,0 Index,Index------------- Column Indices -----------------------  0,-1

   |     Node 1,1        Node 1,2        Node 1,Columns

   |	 Node 2,1        Node 2,2        Node 2,Columns

  Row 

indices     |               |                |

   |        |               |                |

   |

   |	 Node Rows,1     Node Rows,2     Node Rows,Columns

-1,0 --------------------------- Meta data ----------------------  -1, -1

NB The row column indices are basically unlinked nodes keeping track of entry positions and node count

Specific array values used in api

Recursion level:      array[ 0, 0,-1 ]
Solution count:       array[-1, 0, 0 ]
Solution row numbers: array[-1, 1: recursion_level, -1 ]

Node attributes

Name    Description               Value
---------------------------------------
L       Left link pointer           0
R       Right link pointer          1
U       Up link pointer             2
D       Down link pointer           3
LINKED  Node or index link status   4
VALUE   Stores miscellaneous values 5 (-1)

* Unlinking en relinking nodes:

The illustration below which is taken from Wikipedia shows how nodes are covered in algoxtools:
In the example the entry at column 1, row 1 is heuristically chosen to be covered.

Since the nodes at the red ones in Columns (1,4,7) and rows (A,B,C,E,F) are not linked to any other outside nodes, they are unlinked just by row and column index without unlinking each individual node.

In the example the remaining ones in the red boxes, (C5,E2,E3,E6 and F2) are what I call 'loose nodes'.
They are situated in an unlinked row but not in an unlinked column, so they are possibly attached to external nodes and therefore need to isolated ie. unlinked on an individual level
NB common in most other implementations of Algorithm X only the down link of the upper node and the up link of the down nodes are changed, right and left links do not need to be modified since they are not externally referenced.