Finding exact covers in NumPy (and solving Sudoku!)
Project description
Finding Exact Covers in NumPy (and Solving Sudoku!)
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.
As an example, we use this NumPy module to solve Sudoku. As a bonus feature for the Sudoku piece, we also calculate an approximate rating of the puzzle (easy, medium, hard, or very hard).
How to Try It
git clone https://github.com/moygit/exact_cover_np.git
cd exact_cover_np
make
will build everything, install the Python moduleexact_cover_np
, and run all the tests. It'll also show you some examples. To solve Sudoku, say:
sudoku.py < filename.csv
, wherefilename.csv
contains the puzzle as a list of commaseparated values with 0's denoting the blank entries.
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_np
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_np
:
>>> import numpy as np
>>> import exact_cover_np 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], dtype=int32)
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_np
) 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_np
provides the glue code letting us invokedlx
on NumPy arrays. And finally,
sudoku.py
is the example application.
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.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size exact_cover_np0.0.1py3noneany.whl (10.0 kB)  File type Wheel  Python version py3  Upload date  Hashes View 
Hashes for exact_cover_np0.0.1py3noneany.whl
Algorithm  Hash digest  

SHA256  8810dfdefc2cdb217d3326d790df5dd35a83f8d13f4bb6ea8c07de28e264474c 

MD5  7fb43da03faceecbc064d8f9147f5060 

BLAKE2256  4681403d689478dd08b7e2a6b137b965bc76adbc1361a2c534ed6077a5fa1c91 