Solve exact cover problems
Project description
Finding Exact Covers in NumPy
This is a Python 3 package to solve exact cover problems using Numpy. It is based on https://github.com/moygit/exact_cover_np by Moy Easwaran. Jack Grahl ported it to Python 3, fixed some bugs and made lots of small improvements to the packaging.
The original package by Moy was designed to solve sudoku. Now this package is only designed to solve exact cover problems given as boolean arrays. It can be used to solve sudoku and a variety of combinatorial problems. However the code to reduce a sudoku to an exact cover problem is no longer part of this project. It can be found at:
Another project, 'polyomino' by Jack Grahl uses this algorithm to solve polyomino tiling problems. It can be found at:
Summary
The exact cover problem is as follows: given a set X and a collection S of subsets of X, we want to find a subcollection S* of S that is an exact cover or partition of X. In other words, S* is a bunch of subsets of X whose union is X, and which have empty intersection with each other. (Example below; more details on wikipedia.)
This NumPy module uses Donald Knuth's Algorithm X (also known as Dancing Links) to find exact covers of sets. For details on Algorithm X please see either the Wikipedia page or Knuth's paper. Specifically, we use the Knuth/Hitotsumatsu/Noshita method of Dancing Links for efficient backtracking. Please see Knuth's paper for details.
How to Use It
Suppose X = {0,1,2,3,4}, and suppose S = {A,B,C,D}, where
A = {0, 3}
B = {0, 1, 2}
C = {1, 2}
D = {4}.
Here we can just eyeball these sets and conclude that S* = {A,C,D} forms an exact cover: each element of X is in one of these sets (i.e. is "covered" by one of these sets), and no element of X is in more than one.
We'd use exact_cover
to solve the problem as follows:
using 1 to denote that a particular member of X is in a subset and 0 to
denote that it's not, we can represent the sets as
A = 1,0,0,1,0 # The 0th and 3rd entries are 1 since 0 and 3 are in A; the rest are 0.
B = 1,1,1,0,0 # The 0th, 1st, and 2nd entries are 1, and the rest are 0,
C = 0,1,1,0,0 # etc.
D = 0,0,0,0,1
Now we can call exact_cover
:
>>> import numpy as np
>>> import exact_cover as ec
>>> S = np.array([[1,0,0,1,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,0,1]], dtype=np.int32)
>>> ec.get_exact_cover(S)
array([0, 2, 3])
This is telling us that the 0th row (i.e. A), the 2nd row (i.e. C), and the 3rd row (i.e. D) together form an exact cover.
See the file examples.md for more detailed examples of use.
Implementation Overview
The NumPy module (exact_cover
) is implemented in four pieces:
 The lowest level is
quad_linked_list
, which implements a circular linkedlist with left, right, up, and downlinks.  This is used in
sparse_matrix
to implement the type of sparse representation of matrices that Knuth describes in his paper (in brief, each column contains all its nonzero entries, and each nonzero cell also points to the (horizontally) next nonzero cell in either direction).  Sparse matrices are used in
dlx
to implement Knuth's Dancing Links version of his Algorithm X, which calculates exact covers. exact_cover
provides the glue code letting us invokedlx
on NumPy arrays.
The package now has some pure Python modules for helper functions, with the main algorithm in the Conly package exact_cover_impl
.
How to develop
The package uses poetry and most of the setup for development uses that tool.
To install locally (as an editable package):
poetry install
To build:
poetry build
To run tests:
poetry run test
or poetry run doctest
To open a Python shell with the package available:
poetry run python
The exception is running the C unit tests:
make c_tests
Repository
 build/ The location where files are built.
 dist/ The location for fully prepared files.
 exact_cover/ The Python code.
 obj/ Where the compiled C code is going to be output.
 src/ The C sources.
 tests/ Tests for both the Python package and the C code.
 tools/ Code used in analysing and working with the library. This is not distributed with the package.
Acknowledgements
Thanks very much to Moy Easwaran (https://github.com/moygit) for his inspiring work!
Munit aka µnit (https://nemequ.github.io/munit/) is a wonderful unit testing framework for C code.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for exact_cover1.0.1cp310cp310manylinux_2_35_x86_64.whl
Algorithm  Hash digest  

SHA256  b0a1a66d80480c445815acb0a20915067f2e540519e10c9a8ed9ba384938fe35 

MD5  494b6eaedc5b068efabc8454cdfce089 

BLAKE2b256  3075c2a7da0aee0487beba7772f74e3c77222dccad44829007b973783904c41a 
Hashes for exact_cover1.0.1cp310cp310macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  c3d6c26e8d76cfd6f95e7276af3dec3eb769eca4bdea537923bbf172c5e90ed0 

MD5  dfef951fa01390a1013e21dfb99425b8 

BLAKE2b256  d906eefb212febd692b71b84a714cf50da36a491317784786bc13ad8d36b2028 
Hashes for exact_cover1.0.1cp39cp39manylinux_2_35_x86_64.whl
Algorithm  Hash digest  

SHA256  cf23abed98ccffa598f90a4bbfada11fa54db78560d7339e1748fb02be6184b2 

MD5  518482b38398e5dd8efedb6a2ce5021c 

BLAKE2b256  d2ca6a8c645edc1bf30b512180c8f88b8bd8898b9dc6e525f60ff42875d46557 
Hashes for exact_cover1.0.1cp39cp39macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  a13fc15504e686d0f6f827bc9b50230770524cc3942fd8e225026d8227c9ce93 

MD5  176b25ff2c85d20435d20f7e70b99b3d 

BLAKE2b256  fb5ae140853fbab40b19fbd181bae54285c437fd7222e254c5b010deabd8b1e6 
Hashes for exact_cover1.0.1cp38cp38manylinux_2_35_x86_64.whl
Algorithm  Hash digest  

SHA256  2548b21b7f0b5438da4fb0b2f26bb48aceeb8113e9bff622bdeb833c80063121 

MD5  99ccea656325eb012eed24480854d83d 

BLAKE2b256  7d5b437a05d5ef05051e15934ebac06b84612418d865c063ebc3256434e2c222 
Hashes for exact_cover1.0.1cp38cp38macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  f304157fdc276bc87108ad4ccc5e2552e94322ddc8eea59d39e4811c63c9c40d 

MD5  a7b80121bcb894173780091af80745c2 

BLAKE2b256  e7d1cc343b3f9093cbd0dd06b1b9a18d30bac18e9f8c6b18bd48f1c7957e441c 
Hashes for exact_cover1.0.1cp37cp37mmanylinux_2_35_x86_64.whl
Algorithm  Hash digest  

SHA256  41519cf1449371fb0d4cb2388cce0615b9a4c169cd6b3b1c5f00cfead97d0752 

MD5  2d1d3f9ce66188d028512ac04c934a90 

BLAKE2b256  96b3a6c9f59ce5874e95947b8d1ac41bbd683dc60031f87ff900e8b2292e5503 
Hashes for exact_cover1.0.1cp37cp37mmacosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  0d4d71e5fae5b0699d5510945f296befc4baf1f8575b9ff7cc05d659babe1caa 

MD5  50377fbdaad82f3e4e98f80e8a9396e0 

BLAKE2b256  61286c95e3869929085fa682d0ae7737bd8907552717210c3616a2c955705895 