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 j such that the assignment to $x_1,\ldots,x_j,x_i$ was then inconsistent;
# 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 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:

# if j, 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;
# 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=https://archive.org/details/constraintproces00rina
, isbn=1-55860-890-7
, url-access=registration

Constraint programming