Constraint Solver Part 6: Backtrack and Sum constraint

Series: Constraint Solver in Julia

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

We talked a while about one special constraint type: alldifferent and there especially about sudokus.

Let’s get into the next constraint type in this blog and also a small change in backtracking.

Backtracking

First about backtracking. At the moment we use recursion and it’s kind of the obvious choice for it but it has its limitations regarding recursion limit and I normally don’t find it easy to debug.

The first part of this post is how to change it in a way that we don’t use recursion anymore.

There are some ways of doing this:

  • Building an actual tree structure
  • Building a queue which shows the leaf nodes of a tree
  • Basically do the same as recursion but without it

The first one has the obvious disadvantage that we have to save everything but it’s easy to do everything for example not only Depth-First-Search (DFS).

I use the second option in Juniper.jl as we normally use Best-First-Search (BFS) there and we don’t need to store the tree structure. In that case the information of each node is quite small. Only the bounds of each variable so we split a node into two branches like x <= 2 and x > 2. There is no constraint propagation in the sense as we have it here.

In this project we would basically need to save the whole search space for each node which is too much I think.

Therefore I choose option 3. This limits us to DFS which is fine as long as we only deal with satisfiable problems I think.

Okay so how do we do it?

I created a backtrack object which defines what we have done in that particular node or to be more precise any information we need to remove if we need to backtrack:

mutable struct BacktrackObj
    variable_idx        :: Int
    pval_idx            :: Int
    pvals               :: Vector{Int}
    constraint_idx      :: Vector{Int}
    pruned              :: Vector{Vector{Int}}

    BacktrackObj() = new()
end

We want to know which variable we fixed, which possible values this variable had when we started and in which iteration we are in that process. Additionally if we pruned some values we want to know which constraint was involved because we need the indices and then how many values we pruned.

Remember: pruned in ConstraintOutput is just a vector of numbers which show how many values we removed from a variable.

If we call backtrack! we have:

pvals = values(com.search_space[ind])
backtrack_obj = BacktrackObj()
backtrack_obj.variable_idx = ind
backtrack_obj.pval_idx = 0
backtrack_obj.pvals = pvals
backtrack_vec = BacktrackObj[backtrack_obj]

so simple fill the object and at the moment we didn’t prune anything so we leave constraint_idx and pruned empty.

while length(backtrack_vec) > 0
    backtrack_obj = backtrack_vec[end]
    backtrack_obj.pval_idx += 1
    ind = backtrack_obj.variable_idx

We’ve set pval_idx to 0 before so we increase it…