Backmarking Explained

In constraint satisfaction, backmarking is a variant of the backtracking algorithm.

Backmarking works like backtracking by iteratively evaluating variables in a given order, for example,

x _{1,\ldots,x} _{n} . It improves over backtracking by maintaining information about the last time a variable x _{i} was instantiated to a value and information about what changed since then. In particular:

1. for each variable

x _{i} and value a , the algorithm records information about the last time x _{i} has been set to a ; in particular, it stores the minimal index j<i such that the assignment to x _{1,\ldots,x} _{j,x} _{i} was then inconsistent;

1. for each variable

x _{i} , the algorithm stores some information relative to what changed since the last time it has evaluated x _{i} ; in particular, it stores the minimal index k<i of a variable that was changed since then.

The first information is collected and stored every time the algorithm evaluates a variable

x _{i} to a , and is done by simply checking consistency of the current assignments for x _{1,x} _{i} , for x _{1,x} _{2,x} _{i} , for x _{1,x} _{2,x} _{3,x} _{i} , etc.

The second information is changed every time another variable is evaluated. In particular, the index of the "maximal unchanged variable since the last evaluation of

x _{i} " is possibly changed every time another variable x _{j} changes value. Every time an arbitrary variable x _{j} changes, all variables x _{i} with i>j are considered in turn. If k was their previous associated index, this value is changed to min(k,j) .

The data collected this way is used to avoid some consistency checks. In particular, whenever backtracking would set

x _{i=a} , backmarking compares the two indexes relative to x _{i} and the pair x _{i=a} . Two conditions allow to determine partial consistency or inconsistency without checking with the constraints. If k is the minimal index of a variable that changed since the last time x _{i} was evaluated and j is the minimal index such that the evaluation of x _{1,\ldots,x} _{j,x} _{i} was consistent the last time x _{i} has been evaluated to a , then:

1. if

j<k , the evaluation of x _{1,\ldots,x} _{j,x} _{i} is still inconsistent as it was before, as none of these variables changed so far; as a result, no further consistency check is necessary;

1. if

j \geq k , the evaluation x _{1,\ldots,x} _{k,x} _{i} is still consistent as it was before; this allows for skipping some consistency checks, but the assignment x _{1,\ldots,x} _{i} may still be inconsistent.

Contrary to other variants to backtracking, backmarking does not reduce the search space but only possibly reduce the number of constraints that are satisfied by a partial solution.

References

• Book: Dechter , Rina . Rina Dechter

. Rina Dechter. Constraint Processing. Morgan Kaufmann. 2003. 1-55860-890-7. registration.