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 linked-list with left-, right-, up-, and down-links. - This is used in
sparse_matrixto implement the type of sparse representation of matrices that Knuth describes in his paper (in brief, each column contains all its non-zero entries, and each non-zero cell also points to the (horizontally) next non-zero cell in either direction). - Sparse matrices are used in
dlxto implement Knuth's Dancing Links version of his Algorithm X, which calculates exact covers. exact_coverprovides the glue code letting us invokedlxon NumPy arrays.
The package now has some pure Python modules for helper functions, with the main algorithm in the C-only 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.
1 maintainer
Metadata
1 maintainer
Release files for exact-cover 1.5.0
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | |
|---|---|---|---|---|
| exact_cover-1.5.0.tar.gz | 20.4 kB | Without provenance | Details |
Built distributions (wheels)
Total release size: 492.8 kB
Release files / exact_cover-1.5.0.tar.gz
| Download URL | exact_cover-1.5.0.tar.gz |
|---|---|
| Size | 20.4 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
0321bd9c5103c9a1e66ac8430595b22f18d1faa2d9a054f75ada05a28c00cbee
|
|
BLAKE2b-256 checksum How to use checksums |
a6145b622db6f727f8a1f39b3cc4eeae2ebc8ce83038a70bf73056caf7ec3c9b
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.5.1 CPython/3.7.17 Linux/5.15.0-1078-azure
|
Release files / exact_cover-1.5.0-cp311-cp311-win_amd64.whl
| Download URL | exact_cover-1.5.0-cp311-cp311-win_amd64.whl |
|---|---|
| Size | 22.5 kB |
| Tags | CPython 3.11 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
cd78bfb732a19501f72723c4c1d68617f8446fa2a19a265f8f7be5eeedfa2a91
|
|
BLAKE2b-256 checksum How to use checksums |
adfa0f34d30673fc09dd3b11ca6ba3138b5abf2f822340d305d63acdfdbf800f
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.11.9 Windows/10
|
Release files / exact_cover-1.5.0-cp311-cp311-manylinux_2_31_x86_64.whl
| Download URL | exact_cover-1.5.0-cp311-cp311-manylinux_2_31_x86_64.whl |
|---|---|
| Size | 49.8 kB |
| Tags | CPython 3.11 Linux glibc 2.31+ x86-64 |
|
SHA-256 checksum How to use checksums |
87e1367e404a3401c8b4f150497287c05c5e6db1b43912f2191b874bb9c1c6aa
|
|
BLAKE2b-256 checksum How to use checksums |
2e8d27393b82deffbc6ec09926c219380d847998e18369c111e3a58c075699be
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.11.11 Linux/5.15.0-1078-azure
|
Release files / exact_cover-1.5.0-cp311-cp311-macosx_14_0_arm64.whl
| Download URL | exact_cover-1.5.0-cp311-cp311-macosx_14_0_arm64.whl |
|---|---|
| Size | 28.1 kB |
| Tags | CPython 3.11 macOS 14.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
267dd39c55229714e3cf286303580cb586e3328e7d1e4548b25dd61713c8bfbe
|
|
BLAKE2b-256 checksum How to use checksums |
a78245b504b351e000467c835c3890292c2a7e51f729442c9feec456513cf699
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.11.9 Darwin/23.6.0
|
Release files / exact_cover-1.5.0-cp310-cp310-win_amd64.whl
| Download URL | exact_cover-1.5.0-cp310-cp310-win_amd64.whl |
|---|---|
| Size | 22.5 kB |
| Tags | CPython 3.10 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
694aa16fab0a5fab0f6efaf21338c1c4e259a10ea6f380bac0abe03c04663621
|
|
BLAKE2b-256 checksum How to use checksums |
1bc14d794b8d21ac275f1bd882b5f7855a9bb0a3681b54c5f1bf279b8d0c5af0
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.10.11 Windows/10
|
Release files / exact_cover-1.5.0-cp310-cp310-manylinux_2_31_x86_64.whl
| Download URL | exact_cover-1.5.0-cp310-cp310-manylinux_2_31_x86_64.whl |
|---|---|
| Size | 48.8 kB |
| Tags | CPython 3.10 Linux glibc 2.31+ x86-64 |
|
SHA-256 checksum How to use checksums |
1c62a4098914adea40aae72e40ffdc20d863452826c9f616884d3290e0c7a82c
|
|
BLAKE2b-256 checksum How to use checksums |
1d253993e6221876b66369aa400d2b63f307f2970755654e7b6805832149e572
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.10.16 Linux/5.15.0-1078-azure
|
Release files / exact_cover-1.5.0-cp310-cp310-macosx_14_0_arm64.whl
| Download URL | exact_cover-1.5.0-cp310-cp310-macosx_14_0_arm64.whl |
|---|---|
| Size | 28.1 kB |
| Tags | CPython 3.10 macOS 14.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
5bacca44f0b5800f1c342645206d5cb8bdf2a5139cd4c33766b1554913b5ff03
|
|
BLAKE2b-256 checksum How to use checksums |
7b564def5e371f2d4e66f2a8e7302698d33312f430c65c21524282fecfb12daf
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.10.11 Darwin/23.6.0
|
Release files / exact_cover-1.5.0-cp39-cp39-win_amd64.whl
| Download URL | exact_cover-1.5.0-cp39-cp39-win_amd64.whl |
|---|---|
| Size | 22.5 kB |
| Tags | CPython 3.9 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
27fcb2664c7b715c1a6f3f3e3d0801db3984a859c1628be0f074ff971420c3ea
|
|
BLAKE2b-256 checksum How to use checksums |
a388757b8fc31142269cad2e65a0ee1746db54ada2c121db37166e8d10dfcdc8
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.9.13 Windows/10
|
Release files / exact_cover-1.5.0-cp39-cp39-manylinux_2_31_x86_64.whl
| Download URL | exact_cover-1.5.0-cp39-cp39-manylinux_2_31_x86_64.whl |
|---|---|
| Size | 48.6 kB |
| Tags | CPython 3.9 Linux glibc 2.31+ x86-64 |
|
SHA-256 checksum How to use checksums |
84686801b892279198e623a19a28d4dda90652fcfa52e5e0a1e47f28d29f10aa
|
|
BLAKE2b-256 checksum How to use checksums |
e5e14f29ce00f221fb8ce8a54fa59a3534945e46a21fba7835f4a929b0bc95b5
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.9.21 Linux/5.15.0-1078-azure
|
Release files / exact_cover-1.5.0-cp39-cp39-macosx_14_0_arm64.whl
| Download URL | exact_cover-1.5.0-cp39-cp39-macosx_14_0_arm64.whl |
|---|---|
| Size | 28.1 kB |
| Tags | CPython 3.9 macOS 14.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
13d84fcd69f4adc75b49c1f75c09905559f094b3c6246b85f7fce08182466359
|
|
BLAKE2b-256 checksum How to use checksums |
87b0ea883eaab90558daadb0f8d83e019862e19d667ae0a91f0dd97228c928e7
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/2.0.1 CPython/3.9.13 Darwin/23.6.0
|
Release files / exact_cover-1.5.0-cp38-cp38-win_amd64.whl
| Download URL | exact_cover-1.5.0-cp38-cp38-win_amd64.whl |
|---|---|
| Size | 22.3 kB |
| Tags | CPython 3.8 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
a6b6fadd5198ff20d95fa98f319e5dc1c51d3ea13a155286c4d4d2fe0f59a506
|
|
BLAKE2b-256 checksum How to use checksums |
a8264f2b6112cc9356cc318e1b4c3f2efd013b68e78fe1e40e0826daaa05bad5
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.8.5 CPython/3.8.10 Windows/10
|
Release files / exact_cover-1.5.0-cp38-cp38-manylinux_2_31_x86_64.whl
| Download URL | exact_cover-1.5.0-cp38-cp38-manylinux_2_31_x86_64.whl |
|---|---|
| Size | 50.1 kB |
| Tags | CPython 3.8 Linux glibc 2.31+ x86-64 |
|
SHA-256 checksum How to use checksums |
292e72974d1cb1d4ef2c842163ef02975a22b5624ad64b44682faa49cf3018c6
|
|
BLAKE2b-256 checksum How to use checksums |
ce90f8ee3ed5a1e7484cc7bde1c9ceb6891404275a7e263a8bc633c72e6ff502
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.8.5 CPython/3.8.18 Linux/5.15.0-1078-azure
|
Release files / exact_cover-1.5.0-cp38-cp38-macosx_14_0_arm64.whl
| Download URL | exact_cover-1.5.0-cp38-cp38-macosx_14_0_arm64.whl |
|---|---|
| Size | 28.0 kB |
| Tags | CPython 3.8 macOS 14.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
4c689f3612035f4172430930acf0317a479e3975893f99b8657280834b4f33c7
|
|
BLAKE2b-256 checksum How to use checksums |
0b386acfcc84327924148f31b55b26d194a58420019b903d07c9a13722e5c60d
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.8.5 CPython/3.8.10 Darwin/23.6.0
|
Release files / exact_cover-1.5.0-cp37-cp37m-win_amd64.whl
| Download URL | exact_cover-1.5.0-cp37-cp37m-win_amd64.whl |
|---|---|
| Size | 22.3 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Windows x86-64 |
|
SHA-256 checksum How to use checksums |
e5f08c125ec52ef59bcbb9bb856a15187c00d3cfdd574ed80f3557e0922ebffc
|
|
BLAKE2b-256 checksum How to use checksums |
308d32f8968f0ac14a3f511ec9b1e8cc435e2dd0e22381fb635da4af137add30
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.5.1 CPython/3.7.9 Windows/10
|
Release files / exact_cover-1.5.0-cp37-cp37m-manylinux_2_31_x86_64.whl
| Download URL | exact_cover-1.5.0-cp37-cp37m-manylinux_2_31_x86_64.whl |
|---|---|
| Size | 50.7 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Linux glibc 2.31+ x86-64 |
|
SHA-256 checksum How to use checksums |
8fbe37ab4a814309e8aa2881140bbeebfe76ea246dcce3ea0c8fc590b4a198f6
|
|
BLAKE2b-256 checksum How to use checksums |
da0109fefbc96def76e4e4a1b7b96304d7c425add0c5de550b286fd6b7db7990
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.5.1 CPython/3.7.17 Linux/5.15.0-1078-azure
|
Security for exact-cover 1.5.0
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.
