Series: Constraint Solver in Julia

• Part One: Setup and backtracking
• Part Two: Pruning

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

In this part we want to make a minor but important update to the old post as I missed something as well as doing some bechmarking with other constraint programming solvers or specialized sudoku solvers.

Let’s have a look at the video from the last post:

Explanation:

Last time we have set a value while backtracking and then removed values from the search space and maybe set new values due to fixing this single value.

• black: Given values
• blue:
  • beginning: pruned before backtracking
  • later: set or pruned during backtracking (might be wrong)
• green cell: last set by backtracking
• orange cell: pruned by green cell (or later other orange cells)

At that moment I didn’t completely think that through and only when I had a look at the visualization I made I realized that it’s a bit stupid not to further propagate the new changes as well.

That is the only change on the code basis for this post and after that I’ll show you some benchmarking results which will not be that awesome yet as it’s more like a spoiler and preparation for the next post which will be longer.

So after the first pruning in our backtrack function: GitHub Line

we add a part to prune further on the fixed values:

# prune on fixed vals
co_idx = 1
constraint_idxs_dict = Dict{Int, Bool}()
# get all constraints which need to be called (only once)
while co_idx < length(constraint_outputs)
    constraint_output = constraint_outputs[co_idx]
    for fixed_ind in keys(constraint_output.fixed)
        inner_constraints = com.constraints[com.subscription[fixed_ind]]
        for constraint in inner_constraints
            constraint_idxs_dict[constraint.idx] = true
        end
    end
    co_idx += 1
end
constraint_idxs = collect(keys(constraint_idxs_dict))

There we just check which constraints need to be called again and the in a while loop we call the constraints and add constraints to our list if some cell got fixed:

con_counter = 0
# while we haven't called every constraint
while length(constraint_idxs_dict) > 0
    con_counter += 1
    constraint = com.constraints[constraint_idxs[con_counter]]
    delete!(constraint_idxs_dict, constraint.idx)

    constraint_output = constraint.fct(com, constraint.indices; logs = false)
    push!(constraint_outputs, constraint_output)
    push!(constraints, constraint)
    if !constraint_output.feasible
        feasible = false
        break
    end

    # if we fixed another value => add the corresponding constraint to the list
    # iff the constraint will not be called anyway in the list 
    for ind in keys(constraint_output.idx_changed)
        for constraint in com.constraints[com.subscription[ind]]
            if !haskey(constraint_idxs_dict, constraint.idx)
                constraint_idxs_dict[constraint.idx] = true
                push!(constraint_idxs, constraint.idx)
            end
        end
    end
end

Now you might say that looks awful why is that so much code and it seems like we did that already. You know what, you’re damn right.
Therefore the code gets it’s own function prune!(com, constraints, constraint_outputs) and returns feasible, constraints, constraint_outputs and it will also be called in our main solve function directly after calling every constraint function ones.

Additionally I found that we always backtrack from left to right and then pruning isn’t working that well in Sudoku because all the surrounding cells are already fixed.

Therefore…