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)
>>> print(ec.get_exact_cover(S))
[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.
To see the total number of distinct solutions, we can use the function get_solution_count:
>>> ec.get_solution_count(S)
1
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.4.0cp311cp311win_amd64.whl
Algorithm  Hash digest  

SHA256  b41cd1395325eb208161a362387b06cce61dd414e871751e7a3feb94235ad602 

MD5  fd82f802ce4d1f3c4d3677eefc6aab90 

BLAKE2b256  4ed8339cf330759550c634c2e07b8e3553b5a46b6ea175480b363fb375ade70f 
Hashes for exact_cover1.4.0cp311cp311manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  d5cbc366ce1daf3519aafd2fb6d2ebc421dc71b352dd22baa5453f4524d67160 

MD5  b0adf20017920eeff76ea8feae0736fd 

BLAKE2b256  5814de4605f96c36db51bceb469ef22f97dc30bc591bd562dd8e71a49bf6df80 
Hashes for exact_cover1.4.0cp311cp311macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  859d9545ddc5b7792f93478533d93c3acad4d7b858f6936fcae7d664ecdeada8 

MD5  417ed96a3998969b513fc17990a765aa 

BLAKE2b256  0087e533b858c364f893efc9bbfaf58621f5263b06aeae0aa828870582654f5d 
Hashes for exact_cover1.4.0cp310cp310win_amd64.whl
Algorithm  Hash digest  

SHA256  db4d8c17891a1b3e369415fb7392f2b0fb3065e3115026e92b1466458ff92461 

MD5  48df978668a68aad41ffd57fc44b72e0 

BLAKE2b256  5c35a21ea1a81127e2c1ca4894b1fbeb48575a8cd17abaaae22839372acf105f 
Hashes for exact_cover1.4.0cp310cp310manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  8dde4fb1e4878667f7a58555f3e295997167c36bd3c72db5c5d981cea7611d04 

MD5  05700edd2eb3558fded9b63d8bad3af0 

BLAKE2b256  ecac196474d45b9e97f4990a15e67af89c73f47145b5009c9baa30e30d3eb2e0 
Hashes for exact_cover1.4.0cp310cp310macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  5c3f409f7c2b1260578345d707ddf6504597d0885a4edba75586f0bfb74176c4 

MD5  388e625e3044aceea7dc1956d55b90f9 

BLAKE2b256  ec6c6a5d3097651345d151cdc74382d7f9df485de41593f7121d370ed3278d6a 
Hashes for exact_cover1.4.0cp39cp39win_amd64.whl
Algorithm  Hash digest  

SHA256  091254a47753001f2f3821c098655e638301c3221b37826590e61528078fd3ee 

MD5  f1c0a4fe3fca2ffc20ba73baa16dcb75 

BLAKE2b256  2438be7304ded969410d1f2b531b234014c95cc241bb9774ee4300935401792b 
Hashes for exact_cover1.4.0cp39cp39manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  7680dffff5e69f5ec431dc1f65f9badb9cf3d22d1ace22c5b4d248c86d3e469a 

MD5  3a9a720f51c26df5a5c74ccfe956e097 

BLAKE2b256  26b3a9e53a8a93b162f09b5b607fa838039a04641a420996682e063db7e4b746 
Hashes for exact_cover1.4.0cp39cp39macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  9d9dccb4be8beb132fd98ac904e5d42769edbe8090bc6c8c91b6eb5795e1cd28 

MD5  81b503e3688dced5f4a418af42631879 

BLAKE2b256  f07130656230a8cee647ef5ff83dc1850956c73123839d3a8fdc05597016fc72 
Hashes for exact_cover1.4.0cp38cp38win_amd64.whl
Algorithm  Hash digest  

SHA256  867397e767e24aca133386a711b42a2a7dfecc561fa496c30628cb2c68b1b478 

MD5  f9d601a341101102560aafc51a472fa7 

BLAKE2b256  9c045cd538914e6f79883e70716aef566decdee59087b6ba1ee6b0f3a492a723 
Hashes for exact_cover1.4.0cp38cp38manylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  c6b55675205ce6f8a13ea48127046fc6fa04de6d7f535dc46eb6c020002dc2b1 

MD5  7afceff70951efc65069f5ca01d255a9 

BLAKE2b256  0d049bd737074ea95a34f6cce418b4d574f52bb229d2e2e50048bb79e97f4374 
Hashes for exact_cover1.4.0cp38cp38macosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  a05e0ed3f2a9d66487a34ef17fe6f4f743a753769a26940523c87c7bcf10c2fc 

MD5  d18d0444d8d5bdac1ccbad2e9fdc5d36 

BLAKE2b256  d26cd9dbbad4ef8f19a57545c8e69a16578e5de3cb4d636458a3d1cf136b6f66 
Hashes for exact_cover1.4.0cp37cp37mwin_amd64.whl
Algorithm  Hash digest  

SHA256  ea77e068696fb9507c6b98ed5f2eb0e5ad1422ed2abf5a9ffc81c39c0980780d 

MD5  46985126e7e02f2233b46b80f8775f70 

BLAKE2b256  41fb53d0765315f4de56581c3f314b9885f905b1df3784861a5ca6e87c461589 
Hashes for exact_cover1.4.0cp37cp37mmanylinux_2_31_x86_64.whl
Algorithm  Hash digest  

SHA256  9da08df0167d36f88eb03be1d4fb04870d416273ab361c7059af0c9fd34abf3e 

MD5  3fe9b1074ec11fa374ce9cad4760e45d 

BLAKE2b256  ec401bada59c653ea49c11012e44f08717d5543d0ea12dfedde889a18bcdb9a8 
Hashes for exact_cover1.4.0cp37cp37mmacosx_12_0_x86_64.whl
Algorithm  Hash digest  

SHA256  e2945d951b6ac8c4873451d0c6f4957af9480829b517a68b429d2f1edf61c549 

MD5  3dec63838b122101c24f2a3d85afd5b9 

BLAKE2b256  ce1ed35de5dd2e4d2476fc05a24246d21e2135a26c03da03ca139c8cc0146bbb 