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…