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…

ConstraintSolver.jl – Str8ts

This is part 21 of an ongoing series about: How to build a constraint solver?
You might want to check out earlier posts if you’re new.
See first post.

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.

Mostly these posts are about implementing something new in the constraint solver itself or changing the structure like refactoring.
Sometimes it’s just nice to see what we can do with what we have so far. Yesterday I’ve posted a blog post about the table constraint.
I felt that this might be interesting for those of you who are really interested in this project but I think that there are way more people who might be interested in what to do with it than a dry version of how it works. Therefore here you can read the: How to solve Str8ts using our constraint solver without changing the solver 😀

What is Str8ts?

Str8ts is similar to sudoku as it uses the all different constraint as well as it is played on a 9×9 grid.

This is a fairly simple Str8ts so it provides us with a good start.

The rules:

• Each white field has to have a digit in the end
• No digit can appear more than once in each row/col.
• White fields which are connected (no black cell in between) in a row/col must form a straight.

Black cells without a digit are just defining the straight block. With a digit they are also used for the all different constraint of the second rule.

If we have a look at the first col we can immediately fill it.

The one in the upper left can only be 7 or 9 based on the straights constraint and 7 exists already in the column therefore it must be 9.
It’s very similar for the six and the 2 is the only option to create a straight.

Defining the variables

There are always two things we need to define to solve such a puzzle:

What are the variables and what are the constraints?

In sudoku it was very easy as we had 81 variables and 27 constraints no matter what. Here it is a bit more complicated.
We can take some different routes here and mine is probably not the best but hopefully quite simple to understand.

I decided to have 81 variables as well this time ranging from 0-9 this time. Each white field needs to be between 1-9 and each black field which isn’t assigned a number in the starting configuration is set to 0.

Before we have that in code we need to define the…

ConstraintSolver.jl – Table Constraint

This is part 20 of an ongoing series about: How to build a constraint solver?
You might want to check out earlier posts if you’re new.
See first post.

I didn’t only code a Sudoku solver in Python two years ago I also extended it to solve Str8ts. Basically I tried a lot of what I do now again but this time I’m more structured and Julia feels like a much better language for it.
We need the table constraint to solve Str8ts this time and I’ll show you in this post how the constraint works in it’s basics and how you can add your own constraint to the solver.
In the next post I’ll show you how to use the constraint to solve Str8ts and I also want to use this to solve small Eternity puzzles

Normally I have a puzzle in mind which I want to solve and build the constraint around it. This time I looked which constraints might be useful and wanted to do something about scheduling problems as constraint solvers are the most used tool for those problems.

Unfortunately I wasn’t able to find the best strategy to have interval variables inside JuMP. I will think about it next again. The next thing I found was the table constraint which is a really powerful constraint.

Currently we can limit the search space of a single variable easily by just setting bounds like:

@variable(m, 1 <= x[1:5] <= 7, Int)
# or
@variable(m, x[1:5], CS.Integers([1,2,3,4,5,6,7]))

with the table constraint you can define a set of possibilities for several variables combined.
This can be also used to create other constraints by just enumerating all possibilities like all possible combinations which fulfill the all different constraint.

A small example constraint:

table = [
    1 2 3 1 1;
    1 3 3 2 1;
    1 1 3 2 1;
    1 1 1 2 4;
    1 8 3 1 2;
    4 5 5 3 4;
]

@constraint(model, x in CS.TableSet(table))

This concrete set of options can’t be transformed into ==, <= or all different constraints in an easy way.

You’ll see in the next posts how this constraint can be used for solving other puzzles.

Naive way of implementing the constraint

We always need a way to check feasibility and prune values if we got new knowledge.
A very naive way would be to run over all possibilities and check whether the current search space is feasible.

Let’s have a look at the table again:

table = [
    1 2 3 1 1;
    1 3 3 2 1;
    1 1 3 2 1;
    1 1 1 2 4;
    1 8 3 1 2;
    4 5 5 3 4;
]

For pruning: if setting x[1] we can remove the last row and need to check which possible values are only used in this row i.e x[2] = 5 is not used by any other row therefore we can remove it from the search space…