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…