Tag Archives: julia,puzzle,constraint-programming,optimization

Constraint Solver Part 7: Sum constraint speed-up

Series: Constraint Solver in Julia

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:

Hard killer sudoku without backtracking

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

Hard killer sudoku without backtracking two marked cells

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…

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…

Constraint Solver Part 5: Different data structure

Series: Constraint Solver in Julia

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

Let’s do a small recap of what we have done so far.
We’ve created a julia package in the first post and implemented the most basic backtracking for solving a sudoku puzzle. We understood that this is pretty slow as we could use the information after we fixed a cell to a value to find out the values of cells which are connected by a constraint to that cell. In part 3 I described that these new fixes itself can be used further on which gave us a performance improvement again.

In the last post we tried not to make backtracking faster but instead tried to avoid it as much as possible by solving the sudoku in a more human like fashion.

We could now further try to reduce the number of steps we call the now slower alldifferent constraint or make it faster or change the ordering of the calls or fix values in a different ordering, as at the moment we only decide which cell we want to tackle next in backtracking but not on the ordering of how we fix the number in a cell i.e if it has the possible values 5,6,7 it might be reasonable to start with the 7 if we think that it’s more likely based on some heuristics.

What I want to do instead in this post is changing the data structure a bit. We are currently working on a grid which seems to be a good choice for a sudoku or even Str8ts and the 8-queen problem as well as magic squares but it’s not always the case for example it’s stupid for graph coloring so maybe we should just have linear indices internally instead of cartesian indices. Another point is that we are working with a dictionary to represent the values in our search space for each cell but adding and removing to a dictionary sometimes seems quite stupid as we set a cell in backtracking and then reset it and have to fill all the values again it had before. Maybe there is a better data structure. Besides that it seems to be reasonable to have a struct for a variable which can hold some information of that variable maybe something like a name for a country in graph coloring?

Additionally I think it’s quite weird to have a grid and a search space separately if I think about it. The variable could hold the information about being fixed or not.

I found a new idea at MiniCP Part 2 (unfortunately all sites of the website have the same url :/).
MiniCP is a constraint solver used in teaching constraint solving so you might in general be interested at that. Pascal Van Hentenryck who also is the professor of the online about Discrete optimization…