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…