Exact cover solver in Python
Project description
exact cover in Python
an implementation of Donald Knuth's Dancing Links algorithm in pure Python
Usage
pip install exact_cover_py
from exact_cover_py import exact_covers
problem = np.array([
[1, 0, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 0, 0], # <--
[0, 0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 1, 0], # <--
[0, 1, 1, 0, 0, 0, 1],
[0, 1, 1, 0, 0, 1, 1], # <--
[0, 1, 0, 0, 0, 0, 1],
])
# exact_covers returns a generator of solutions
# one solution
print(next(exact_covers(problem)))
[1, 5, 3]
# all solutions
print(list(exact_covers(problem)))
[[1, 5, 3]]
# number of solutions
def mylen(iterable):
return sum(map(lambda x: 1, iterable))
print(mylen(exact_covers(problem)))
2
Development
# build and install locally with tests dependencies
pip install -e .[tests]
pytest
Building and publishing
# deps
pip install build hatchling twine
# build
python -m build
# publish
twine upload dist/*
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
exact_cover_py-0.0.4.tar.gz
(6.1 kB
view hashes)
Built Distribution
Close
Hashes for exact_cover_py-0.0.4-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e7136931a81171fc43602d4b49cb819bcc39a49c0c4df787dd1abc3dd423971e |
|
MD5 | 83f059ad366e64ee585bb15f460f8972 |
|
BLAKE2b-256 | 06714395e0783eb6082cebe3030fe0910f1029c384bc1d659f06746b34fda49d |