Backmarking

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:

# 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
# 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

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:

# if
# 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

*cite book
first=Rina
last=Dechter
title=Constraint Processing
publisher=Morgan Kaufmann
year=2003
url=http://www.ics.uci.edu/~dechter/books/index.html
id=ISBN 1-55860-890-7