Misplaced Pages

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, ${\displaystyle x_{1},\ldots ,x_{n}}$. It improves over backtracking by maintaining information about the last time a variable ${\displaystyle x_{i}}$ was instantiated to a value and information about what changed since then. In particular:

1. for each variable ${\displaystyle x_{i}}$ and value ${\displaystyle a}$, the algorithm records information about the last time ${\displaystyle x_{i}}$ has been set to ${\displaystyle a}$; in particular, it stores the minimal index ${\displaystyle j<i}$ such that the assignment to ${\displaystyle x_{1},\ldots ,x_{j},x_{i}}$ was then inconsistent;
2. for each variable ${\displaystyle x_{i}}$, the algorithm stores some information relative to what changed since the last time it has evaluated ${\displaystyle x_{i}}$; in particular, it stores the minimal index ${\displaystyle k<i}$ of a variable that was changed since then.

The first information is collected and stored every time the algorithm evaluates a variable ${\displaystyle x_{i}}$ to ${\displaystyle a}$, and is done by simply checking consistency of the current assignments for ${\displaystyle x_{1},x_{i}}$, for ${\displaystyle x_{1},x_{2},x_{i}}$, for ${\displaystyle 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 ${\displaystyle x_{i}}$" is possibly changed every time another variable ${\displaystyle x_{j}}$ changes value. Every time an arbitrary variable ${\displaystyle x_{j}}$ changes, all variables ${\displaystyle x_{i}}$ with ${\displaystyle i>j}$ are considered in turn. If ${\displaystyle k}$ was their previous associated index, this value is changed to ${\displaystyle min(k,j)}$.

The data collected this way is used to avoid some consistency checks. In particular, whenever backtracking would set ${\displaystyle x_{i}=a}$, backmarking compares the two indexes relative to ${\displaystyle x_{i}}$ and the pair ${\displaystyle x_{i}=a}$. Two conditions allow to determine partial consistency or inconsistency without checking with the constraints. If ${\displaystyle k}$ is the minimal index of a variable that changed since the last time ${\displaystyle x_{i}}$ was evaluated and ${\displaystyle j}$ is the minimal index such that the evaluation of ${\displaystyle x_{1},\ldots ,x_{j},x_{i}}$ was consistent the last time ${\displaystyle x_{i}}$ has been evaluated to ${\displaystyle a}$, then:

1. if ${\displaystyle j<k}$, the evaluation of ${\displaystyle 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;
2. if ${\displaystyle j\geq k}$, the evaluation ${\displaystyle x_{1},\ldots ,x_{k},x_{i}}$ is still consistent as it was before; this allows for skipping some consistency checks, but the assignment ${\displaystyle 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

• Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7.

• Constraint programming