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 will be published separately in the future.

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 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], 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) 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_matrix to 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 dlx to implement Knuth's Dancing Links version of his Algorithm X, which calculates exact covers.
exact_cover provides the glue code letting us invoke dlx on NumPy arrays.

Acknowledgement

Thanks very much to Moy Easwaran (https://github.com/moygit) for his inspiring work!

Release files for exact-cover 0.2.1

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for exact-cover 0.2.1
File	Size	Uploaded
exact_cover-0.2.1.tar.gz	10.4 kB	Jan 10, 2021	Details

Built distribution (wheel)

Table of built distributions (wheels) for exact-cover 0.2.1
File	Interpreter	ABI	Platform	Reset
exact_cover-0.2.1-cp37-cp37m-manylinux2014_armv7l.whl 42.6 kB Jan 10, 2021	CPython 3.7	CPython 3.7 pymalloc	Linux glibc 2.17+ ARMv7l	Details

Total release size: 53.1 kB

Release files / exact_cover-0.2.1.tar.gz

Download URL	exact_cover-0.2.1.tar.gz
Size	10.4 kB
Tags	Source
SHA-256 checksum How to use checksums	`8550cec7f15de46eb4f4851e6c5b15aeae5dd17c635ab233e732b9292a454581`
BLAKE2b-256 checksum How to use checksums	`7155e36e4683a15ed403982df289e16aed60e7793c92bf939b09522eb2296d9e`
Upload date	Jan 10, 2021
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`poetry/1.1.4 CPython/3.7.3 Linux/5.4.72-v7+`

Release files / exact_cover-0.2.1-cp37-cp37m-manylinux2014_armv7l.whl

Download URL	exact_cover-0.2.1-cp37-cp37m-manylinux2014_armv7l.whl
Size	42.6 kB
Tags	CPython 3.7 CPython 3.7 pymalloc Linux glibc 2.17+ ARMv7l
SHA-256 checksum How to use checksums	`92ba7f2e7e1f4cada9ea8778465200a81fb5aae5c5ac82294c62e07718d71145`
BLAKE2b-256 checksum How to use checksums	`199d7216a9209c3f5d2a5a2dad1dd3fd7192c3fcb165440196f4150fa1537c33`
Upload date	Jan 10, 2021
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`poetry/1.1.4 CPython/3.7.3 Linux/5.4.72-v7+`