Series: Constraint Solver in Julia

• Part One: Setup and backtracking
• Part Two: Pruning
• Part Three: Pruning+Benchmarking
• Part Four: Alldifferent constraint
• Part Five: Better data structure
• Part Six: Sum constraint first part

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

Last time we introduced the equal sum constraint (eq_sum) and figured out that it isn’t that fast to solve a hard killer sudoku with it.

Last time we ended up with this if we don’t backtrack:

Remark:

• a killer sudoku has the same constraints as a normal sudoku
• plus the constraint that each colored region must add up to the number shown in the top left of that region

I talked about some ideas of how we might be able to further prune the search space:

• Combining sum constraint with all different constraint
  • i.e bottom left 7,8,9 + 7,8,9 should add up to 16 but it is inside same all different => no 8 possible
• Use the sum constraint of row, column or block add up to 45
  • bottom right block: We can have an additional constraint that the red marked cells add up to 9

First what is our current benchmark result for this problem?
My setup:

• 6 core Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz
• Julia 1.2

julia> @benchmark main(;benchmark=true)
BenchmarkTools.Trial: 
  memory estimate:  44.83 GiB
  allocs estimate:  317941771
  --------------
  minimum time:     42.523 s (18.96% GC)
  median time:      42.523 s (18.96% GC)
  mean time:        42.523 s (18.96% GC)
  maximum time:     42.523 s (18.96% GC)
  --------------
  samples:          1
  evals/sample:     1

and this is the info:

Info: 
pre_backtrack_calls = 77
backtracked = true
backtrack_counter = 87829
in_backtrack_calls = 4136981

Okay let’s start with a very simple version:

If there are only two unfixed variables in a sum constraint we test all options and check whether it’s feasible or not i.e if the possibilities are [1,4] and [1,2,3,4] and the sum should equal 5 we currently don’t prune anything as we normally only prune the outside values but we clearly can reduce the possibilities of the second variable to [1,4] as well.

We check first how many unfixed variables there are and save the indices (both the normal index of the variable and the local index for pruned).

# if there are only two left check all options
n_unfixed = 0
unfixed_ind = zeros(Int,2)
unfixed_local_ind = zeros(Int,2)
unfixed_rhs = constraint.rhs
li = 0
for i in indices 
    li += 1
    if !isfixed(search_space[i])
        n_unfixed += 1
        if n_unfixed <= 2
            unfixed_ind[n_unfixed] = i
            unfixed_local_ind[n_unfixed] = li
        end
    else
        unfixed_rhs -= value(search_space[i])
    end
end

Then we check whether we have n_unfixed == 2 and if that is the case:

for v in 1:2
    if v == 1
        this, local_this = unfixed_ind[1], unfixed_local_ind[1]
        other, local_other = unfixed_ind[2], unfixed_local_ind[2]
    else
        other, local_other = unfixed_ind[1], unfixed_local_ind[1]
        this, local_this = unfixed_ind[2], unfixed_local_ind[2]
    end
    for val in values(search_space[this])
        if !has(search_space[other], unfixed_rhs-val)
            rm!(search_space[this], val)
            changed[this] = true
            pruned[local_this] += 1
        end
    end
end

This means we iterate through all possibilities for…