Show HN: Miniexact – An efficient DLX Exact-Cover solver with a Python interface(github.com)

2 pointsby maximaximalhace 11 meses0 comments

Show HN: Miniexact – An efficient DLX Exact-Cover solver with a Python interface

https://github.com/miniexact/miniexact

I've been hacking on this project for quite a while and now finally released it on PyPI for Linux, MacOS and Windows! The release includes a binary (miniexact) that solves exact cover problems in your terminal, and a similarly named Python module you can use to encode problems. Everything is implemented in C without any other dependencies, so this compiles cleanly on every system. You can select the algorithm you want to use in the console or use the Web-UI.

I haven't found a faster solver yet in my benchmarks, so I would be happy to see other implementations! The big caveat is that it still purely relies on the Dancing Links technique and not on the newer Dancing Cells from Christine Solnon and the TAOCP Fascicle 7. While my implementation has a different memory architecture than the standard one (arrays of fields instead of an array of node structs each containing the same fields), this could be an interesting addition to the provided algorithms. There is nothing preventing this addition but the involved implementation effort.

Would be nice to read some thoughts about Exact-Cover and the problems you solve with it! Maybe this project encourages somebody to look at this nice paradigm again :)

0 comments

—