#BACKTRACK MENTOR OHIO HOW TO#
#BACKTRACK MENTOR OHIO SERIES#

# we changed the search space and fixed values but didn't turn out well That means that we need to also reset our last_ptr and first_ptr for that variable back to what it was before and remove the backtrack object from our list.Īt the end of our while loop we had: status = rec_backtrack!(com) If backtrack_obj.pval_idx > length(backtrack_obj.pvals)Ĭom.search_space.last_ptr = length(backtrack_obj.pvals) Now we check whether we tested all possible values already: # checked every value => remove from backtrack Now there might be something we pruned before and need to revert now (not in the first call of the while loop) if isdefined(backtrack_obj, :pruned) We've set pval_idx to 0 before so we increase it by one here and we will use ind to refer to the index of the variable as we did before. So simple fill the object and at the moment we didn't prune anything so we leave constraint_idx and pruned empty. If we call backtrack! we have: pvals = values(com.search_space)īacktrack_vec = BacktrackObj Remember: pruned in ConstraintOutput is just a vector of numbers which show how many values we removed from a variable. 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. 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. 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 This limits us to DFS which is fine as long as we only deal with satisfiable problems I think. In this project we would basically need to save the whole search space for each node which is too much I think. There is no constraint propagation in the sense as we have it here. Only the bounds of each variable so we split a node into two branches like x 2. In that case the information of each node is quite small. 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. 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).

#BACKTRACK MENTOR OHIO HOW TO#

The first part of this post is how to change it in a way that we don't use recursion anymore.īuilding a queue which shows the leaf nodes of a treeīasically do the same as recursion but without it 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. Let's get into the next constraint type in this blog and also a small change in backtracking. We talked a while about one special constraint type: alldifferent and there especially about sudokus.

#BACKTRACK MENTOR OHIO SERIES#

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

Backtrack mentor ohio