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=bool)
>>> 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.2.1cp311cp311win_amd64.whl
Algorithm  Hash digest  

SHA256  941bd9c31b3fe4a1b7036ccc8eaadb134a66ee3b4f9299f16c0d473708c77bd5 

MD5  933c19e0e7063a11d4c1d9d5f5609bb7 

BLAKE2b256  24ebcb415c65ca8418e1386c001dade75ef85626cceff24b4e01727c47fa1663 
Hashes for exact_cover1.2.1cp311cp311manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  75a5420ca5c2f6c92bc650142bb29f19dfdc77e84b9d902cff17f8d6909e60ca 

MD5  2e58ba6e5e287baef8dd2716333ee985 

BLAKE2b256  2c431fe0b224095ecffb13c1549b0c951802505dc6e691646fe6db8ee3ec4ef4 
Hashes for exact_cover1.2.1cp311cp311macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  725da33f4f3892d7c42008689c788bd6c21b751dd65e3e4d4fd15e3921d0e8c6 

MD5  192924106cd8eb72351009c236521432 

BLAKE2b256  f1b86c7a91cc97ad67cd608059bac09709806c0deb5c970e5a982b1ffa3a6c5b 
Hashes for exact_cover1.2.1cp310cp310win_amd64.whl
Algorithm  Hash digest  

SHA256  97e0c10e01179122854f5d01b82ec0b6115fda7c6df81cddc4e9f8ca64c66380 

MD5  a266a5c72df188847669791db7eef500 

BLAKE2b256  e4844d1ab0b3ad9c318a1f8cc1bb62534d36e6a5a9fc7e22f6cffffff27d64b9 
Hashes for exact_cover1.2.1cp310cp310manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  55a671724e094b6a7e0767ad73aefd9edff0afe01418f614233dc09d1dc75a68 

MD5  e8fa371bebed17f7413e5912d2dc78fe 

BLAKE2b256  74f57d363c67eda9912981490b3f1614e46e0fcbf2f336c38dd2fe956d21d98d 
Hashes for exact_cover1.2.1cp310cp310macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  c9f124ae3c0961045e19d592231286d01157c8ca2c79162f849e70d6e4bd4325 

MD5  8121a404fc1f37d0e0cb631bf92457f8 

BLAKE2b256  de4c98063311338e3738dc41e2845946684594f9ce225cece24b3e14f1a41a85 
Hashes for exact_cover1.2.1cp39cp39win_amd64.whl
Algorithm  Hash digest  

SHA256  710c2f5d3cee6691c32b334e1d2b7804b857ac73b1e1cc11b38882251d659ce9 

MD5  534581d1b4520799497f527cbf54cf35 

BLAKE2b256  17eeb277692e49628d6012de906730655bb53b05df18a81e3f054c2ba5e804d5 
Hashes for exact_cover1.2.1cp39cp39manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  745f56afbd8109c638f174feb343021b6d7eb7a2c31ff5be53c53b756ec7ab1d 

MD5  4f4deea1c8a1b056dd1866dec9f64544 

BLAKE2b256  80d27f0810c1e1bf25529cdf1a3479539e320692033ecc79eb8cdf8359554042 
Hashes for exact_cover1.2.1cp39cp39macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  8d64f585b9cad0ea2de81afcdff859c6b354bcc2a4473580fa27edccbf7b208a 

MD5  cfc0157394972a4caaf94899c6db0de2 

BLAKE2b256  0e10c1afedeedd2d22ac0256f43034b6211302c9740ab1f2a6e46d9cde5523ab 
Hashes for exact_cover1.2.1cp38cp38win_amd64.whl
Algorithm  Hash digest  

SHA256  e0c9a1bee7f9dbd154c9a1e27c86d84f835f685c6dfe35426512f96eec799f29 

MD5  cd070dcdbd100655c9ac6f2bb8ab4950 

BLAKE2b256  41bdc027883e61d2c4bb79f902f1b69cb355fc80451d7b3e4c5ea87fa9386861 
Hashes for exact_cover1.2.1cp38cp38manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  04b6f08140f15319ba2018622767c69419de3809707d6a0b4c1161518fb4c6d6 

MD5  aa83f350c2def8050aecbfe81bfd45d7 

BLAKE2b256  dfa8103256130d44571427a927f8566e7c8696961b4c29c2321f98ea843c3ce9 
Hashes for exact_cover1.2.1cp38cp38macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  d166d5df232ca02eaf2e25f5949fa44cbcc40e2d12a7a1e0b7d43ce2d1cdeebd 

MD5  d06eb6f6fb1b7104de441d6db5f85302 

BLAKE2b256  d6489824e3ecbf69f7dace95173b5c4dea2ca60088ede20d901fe4ec976ba305 
Hashes for exact_cover1.2.1cp37cp37mwin_amd64.whl
Algorithm  Hash digest  

SHA256  b9d10c3576b63862c17ee566c4dbac8a46232ef35ec10d166bf0e1794d5f41d0 

MD5  b514bdf0f9e28498f48cba9b672b97de 

BLAKE2b256  08a8f60117c0ca14b127a82a31ef82d6bca627d3e88c32cefd11df46e40bb57f 
Hashes for exact_cover1.2.1cp37cp37mmanylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  a77c1da8605b6386a50e3e9f2a435def329966e40c2c66e14268955010c5349e 

MD5  bd5c7d3cb0d1414f0edfa9cb80eeb63d 

BLAKE2b256  fa8d983009d2cb09d0ac350b7ad41a8f1705a9e0401e71f1cc812caf00b863ab 
Hashes for exact_cover1.2.1cp37cp37mmacosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  87bd306ee225c6112b36bcd3f426ff401ac7d6b62be951653b1c285a551d7351 

MD5  892d4bb7f4b50df91bc30634b97fb7ce 

BLAKE2b256  159544da4f8112b9d53d6419137ba6b1514fc4177a5b0bada649812d75aca216 