ConstraintSolver.jl – Bugs & Benchmarks
This is part 22 of an ongoing series about: How to build a constraint solver?
You might want to check out earlier posts if you’re new but this part is one of the parts that can be read by itself (mostly).
See first post for a list of other posts in this series.
In short:
I’m creating a constraint solver from scratch in Julia. You can follow the project on my GitHub repo.
Whenever I add something not too small I’ll post about it in my blog. Sometimes I also make a post of small stuff when there is enough of it.
If you’re interested in some special thing which you don’t understand please open an issue and I’ll explain my thoughts.
Some people mentioned a while ago that it might be nice to publish version v0.1.0 even though this project misses a lot of things at the moment.
For those of you who are interested in trying things out it should be easier this way. Just ] update in the REPL and you can try the newest stuff.
Okay you should run ] add ConstraintSolver before 😉
That was about a month ago and now ConstraintSolver.jl is already at v0.1.6 so what happened? 😀
Biggest new feature is the table constraint which I described in this blog a few weeks ago.
The rest is basically bugfixes and then v0.1.6 which implements a few new “features”.
It’s probably best to go through it chronologically as it is a bit of a story.
Oh have you missed my newest YouTube video?
Profiling
After the video I wanted to profile the code to see where the most time is spent. I had a look at my profiling post to check how the commands again. I found that something doesn’t run the way I thought it would (actually I didn’t think much about it…).
In the Eternity II puzzle there are a lot of x == y constraints and I thought okay I’ve created the EqualSet constraint a while ago so that will be used. Well no…
Of course not. Code does exactly what you typed and not what you intended which will be happening more than once in this post.
EqualSet
It uses the LinearConstraint which is a bit overblown for it. Therefore I decided that x == y will be interpreted as [x,y] in CS.EqualSet(2). Which made my code incredibly…
Yeah you guessed it right: Slow!
Wasn’t hard to figure out that my pruning strategy was basically non existent. If x has possible values [2,3] and y [3,4] I returned feasible and did nothing because they are not fixed. Always check whether you can’t prune more! 😉 Well here the problem was I never really used that constraint…
My idea was first to use intersect but that is exactly the part that was slow based on my profiling before. Therefore I decided to do intersect before pruning to have it correct once and then…