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:
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 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 (Example)
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='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.
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.
Repository
 build/ The location where files are built.
 dist/ The location for fully prepared files.
 exact_cover/ The build tool 'poetry', seems to need this folder with a dummy python file so it doesn't worry about there not being any package.
 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.
Acknowledgement
Thanks very much to Moy Easwaran (https://github.com/moygit) for his inspiring work!
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 Distribution
Hashes for exact_cover0.6.0a1cp37cp37mmanylinux2014_armv7l.whl
Algorithm  Hash digest  

SHA256  15c1f2a12b1782588aa862cb0755f48a4010c5ab64543010a36d925aa5d04622 

MD5  8bc6a10e0ce6be23799ceb6d5a8f54f3 

BLAKE2b256  9a4b4d2f1e884d5172a6aa576ac52929fcc7ceccfe90fc3c79f8ef1df151dc0a 