Series: Constraint Solver in Julia

• Part One: Setup and backtracking

This is part 2 of the series about: How to build a Constraint Programming solver?

The first part got more attention in the first two days than I thought. Thanks for that 😉 If you want to keep on notified about updates the best thing is to follow the blog on Twitter @Opensourcesblog.

In this post I’ll use a different Sudoku than last time as the last time turned out to be relatively easy:

grid[1,:] = [0 0 0 0 0 0 0 0 0]
grid[2,:] = [0 1 0 6 2 0 0 9 0]
grid[3,:] = [0 0 2 0 0 9 3 1 0]
grid[4,:] = [0 0 4 0 0 6 0 8 0]
grid[5,:] = [0 0 8 7 0 2 1 0 0]
grid[6,:] = [0 3 0 8 0 0 5 0 0]
grid[7,:] = [0 6 9 1 0 0 4 0 0]
grid[8,:] = [0 8 0 0 7 3 0 5 0]
grid[9,:] = [0 0 0 0 0 0 0 0 0]

In the current version I have the following benchmark results:

julia> @benchmark main(;benchmark=true)
BenchmarkTools.Trial: 
  memory estimate:  686.05 MiB
  allocs estimate:  19347707
  --------------
  minimum time:     882.354 ms (12.26% GC)
  median time:      953.116 ms (12.70% GC)
  mean time:        940.299 ms (13.98% GC)
  maximum time:     981.150 ms (19.88% GC)
  --------------
  samples:          6
  evals/sample:     1

Info: I’ve added the ;benchmark parameter to my current script to avoid output if benchmarking.

In this post we want to bring it down to something around 15ms but to do that we first must understand why the current version is slow. I mean if we call 0.9s slow but based on my experience it is, as I know that we can improve it much more.

There are several points:

• We are currently not solving it like a human being
  • This doesn’t necessarily have to be our goal if we find a better alternative but might give us some hints
• We only fix the basics and then we do some kind of trial and error

Let’s have a look at the search space without backtracking

We fix a single number and 54 spots are still open. The backtrack function is called 62264 times. That is a crazy amount.
Now we could try to think about how we remove more values from the search space before we start the backtracking and we will do that in the next post.

For this post we try to prune (remove values) while we are doing backtracking.

Before we start with that I want to do some small things I saw after publishing the post:

1. I want to have some information about the solve call like whether backtracking was needed, how many constraint calls we had before backtracking and how often the backtracking function was called.
2. I sometimes only wrote [] instead of Int[] for example.
3. At the moment sometimes a constraint is called even though nothing changed since last…