multiple solutions

[parmentelat]

probably related to #17 and #18:

my understanding from reading the readme, and because get_exact_cover() is the only symbol exposed in the exact_cover package, is that we can only ask for one solution

is that correct, or is there any way we can iterate on them all ?

in any case, the readme might deserve a few words about that imho :)

[jwg4]

The answer is that currently, the library only returns the first solution.

The C code could probably be adapted reasonably easily to return all solutions. but I haven't done it yet.

you are right that this should be made clear in the readme

[jwg4]

@parmentelat I am planning to add the functionality to this package, is there any chance that you would be interested in participating in this effort?

I believe I am able to carry out this work but any level of help would be really appreciated - testing the new version against reasonably large problems is a good example of something that would be very helpful.

Also tagging @johnrudge in case he would like to be involved.

[parmentelat]

@jwg4

yes sure I can contribute, in the form of tests for sure, and maybe more even if my C is a little rusty ;)

[parmentelat]

may I suggest that you call the new wip function get_all_solutions() plural ?

[jwg4]

Yes, you are right, this would be better

[parmentelat]

hi there
for the record, I have been toying with this algorithm too and wrote a pure Python implementation:
https://github.com/parmentelat/exact-cover-py
https://pypi.org/project/exact-cover-py/

which is 20-60 times slower than this C one - that was expected - but that returns all solutions as a generator, which can be more flexible when tackling large problems

for the tests/ area I have mimicked and extended the contributions that I made in the present repo, it is maybe something where we could cooperate; in particular I might be recording there all the solutions to the pentominoes-derived problems (chessboard with an additional 2x2, and 5x12, for starters)

still for the record, I had toyed with the idea of going for Rust instead, but could not find a decent way to expose a generator, which was my primary goal, hence the choice of Python

[jwg4]

Thanks for this. I think it would be a great idea to pool testing resources - although I'm not yet sure of the best way of doing this. Perhaps there should be a pypi package with test cases which would be a dev-only dependency of both packages? I see there as being at least two types of test cases: those where we want to check a (possibly complex) set of solutions, and those where we just want to make sure the solver does not crash or cause an exception. The latter could include various edge cases like problems with only one row, very large number of solutions, etc. The former would require at least some code which deals with differences in how the solutions are produced, for example the same solutions in a different order. I haven't had time to work on this recently, but I probably can put together a hacky version of get_all_solutions which works, but which might be 2 times slower then it could be. This still might be interesting to you if your next best alternative is 20 times slower? Are you interested in using a generator because you want to reduce use of RAM by processing some solutions before you generate the next ones? I haven't checked that exact-cover performs correctly in this way, but it is definitely something I will try and add.

…

On Wed, 10 Jan 2024, 09:11 parmentelat, ***@***.***> wrote: hi there for the record, I have been toying with this algorithm too and wrote a pure Python implementation: https://github.com/parmentelat/exact-cover-py https://pypi.org/project/exact-cover-py/ which is 20-60 times slower than this C one - that was expected - but that returns all solutions as a generator, which can be more flexible when tackling large problems for the tests/ area I have mimicked and extended the contributions that I made in the present repo, it is maybe something where we could cooperate; in particular I might be recording there all the solutions to the pentominoes-derived problems (chessboard with an additional 2x2, and 5x12, for starters) still for the record, I had toyed with the idea of going for Rust instead, but could not find a decent way to expose a generator, which was my primary goal, hence the choice of Python — Reply to this email directly, view it on GitHub <#70 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABGTQCGDDUZJB3V4G4ED3KTYNZLNNAVCNFSM6AAAAAA6KATGBGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQOBUGQ2TIOBXGA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[jwg4]

Maybe you have a good reason why you can't use a C++ implementation in a python package? And therefore an improvement to exact_cover would not be interesting to you.

If this is related to any problems building exact_cover, let me know. It might be something fixable, or perhaps you could be helped by adding binary distributions for different systems? Eg we have a package for ARM architecture in a repository for that.

[parmentelat]

I think it would be a great idea to pool testing resources - although I'm
not yet sure of the best way of doing this. Perhaps there should be a pypi
package with test cases which would be a dev-only dependency of both
packages?

I was more thinking of sharing a wide enough range of problems and their solutions..
indeed it could come with some way to canonicalize solutions (a set of sorted tuples comes to mind); but each lib would then use that as needed...

I haven't had time to work on this recently, but I probably can put
together a hacky version of get_all_solutions which works, but which might
be 2 times slower then it could be. This still might be interesting to you
if your next best alternative is 20 times slower?

my angle here is purely abstract; the reasons why I have gone for a Python version are, in no particular order :

• that I was puzzled to see that your C code required essentially to rewrite search just to get a count of solutions; and iiuc you're going to have to write a third one for gathering all solutions (am I getting that right); while writing this as a generator is much more elegant as it requires only one code...; it would also allow to dig into much larger problem spaces...
• I was interested in rewriting the algorithm myself so as to be sure I have a thorough understanding of all the nuts and bolts involved; at some point I even considered rewriting it in Rust; after some research I gave up this track though; apparently there is no (not yet ?) mechanism in Rust to implement generator functions like Python has them, meaning that one needs to manually implementing some sort of state management; and in our case the state is the stack...
• along the same kind of lines, I have used this Python code to benchmark other runtimes, like e.g. pypy, and I plan on giving a try with mojo too, to see how that beast behaves on this particular code.
• I've also messed with the S heurisitic a bit (that one I could have done on your code I guess), but clearly on our 2 pentominoes examples, without the heuristic the algorithm seems to go south badly..

so as you see, I have taken this as a pretext for playing with this topic, my concerns are purely intellectual and theoretical, and not that much practical... ; typically all this will end as an assignment for some of my students ;-)

now if you do implement a get_all_solutions() function, I'll be happy to share my current set of test problems so that we can double check our respective results :-)

ps. to answer your other question, I can't remember exactly what I did, but I no longer face any build problem, at least this is workable

[johnrudge]

Like @parmentelat , I've had a go at coding up my own exact cover solver from scratch. My efforts are here:
https://github.com/johnrudge/xcover
Like @parmentelat my solver is pure python and gives you a generator, but I've used numba to accelerate the main algorithm. Neglecting the overhead from numba's initialisation, I think the raw performance is fairly comparable to the C extension in exact_cover, although I haven't done any detailed benchmarking.

[jwg4]

hi @parmentelat, @johnrudge. Version 1.4.0a1 is now on pypi and has a working implementation of get_all_solutions. The function returns a set of tuples.

Any feedback welcome!

I will promote the prerelease version to a real version when I've updated the documentation.

[jwg4]

fixed by #78

[johnrudge]

cover_speed_test.zip

exact_cover solve in 4.56281722499989 s
xcover solve in 0.06379091800044989 s
xcover faster by factor of 71.52769340876564

Thanks @jwg4 for adding this to the package. I've had a quick play, and I think it works fine, but at the moment it seems rather slow. On an example I've been playing with (attached above) it runs around 70 times slower than the covers_bool function in xcover. I don't where the slow performance comes from -- I would expect your C code to run at a similar kind of speed. I think it does run at a similar speed for finding a single solution, just not for multiple solutions.

[jwg4]

Thanks a lot for taking a look @johnrudge !

I'll look into this example and see if there's a reason it's so slow. I'm also keen to see the details of xcover and how it works.

[parmentelat]

@jwg4
as discussed I have published a separate Python package that comes with a few exact cover problems and their solution
you can find it here
https://pypi.org/project/exact-cover-samples/
and that might help shorten your test code; for example the tests for exact_cover_py are now a few tens of lines here
https://github.com/parmentelat/exact-cover-py/blob/main/tests/test_problems.py

if you'll allow it I might add in these samples more of your own inputs (the sudoku-based ones for example). tell me how that sounds

---

@johnrudge

sorry but for now these samples are only regular boolean problems with no secondary items nor colors..

I'd like to thank you as well because I was not aware of these developments :)
in light of all this I have rewritten https://github.com/parmentelat/exact-cover-py/ to use
algorithm X as described in section 7.2.2.1 of taocp, which I could much more easily compile with numba just like you did, and come much closer in terms of execution speed

I have learned a lot about numba in the process, which was my main topic of interest;
I have no plans on developing exact-cover-py any further, since xcover is both faster and more powerful thanks to algo C :)

---

regardless, as of now here's a benchmarking between the 3 libs, as produced by a utility in exact-cover-samples/
the job is always to compute all solutions of a given problem
right now most of the problems just don't get through with exact-cover, it will be interesting to run again once @jwg4 publishes his fixes