Backmarking

Quality 0.50 · 4 views · Updated 2 months ago

title: "Backmarking" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["constraint-programming"] topic_path: "general/constraint-programming" source: "https://en.wikipedia.org/wiki/Backmarking" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

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:

::figure[src="https://upload.wikimedia.org/wikipedia/commons/e/eb/Backmarking-1.png" caption="An example, in which search has reached x_i=d the first time."] ::

  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 such that the assignment to x_1,\ldots,x_j,x_i was then inconsistent;
  2. 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.

::figure[src="https://upload.wikimedia.org/wikipedia/commons/3/3b/Backmarking-2.png" caption="When search reaches x_i=d for the second time, part of the path is the same as the first time."] ::

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 ij 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, 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;
  2. 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 |authorlink = Rina Dechter | title=Constraint Processing | publisher=Morgan Kaufmann | year=2003 | url=https://archive.org/details/constraintproces00rina | isbn=1-55860-890-7 | url-access=registration

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

constraint-programming