page_title: Backmarking
hierarchical_section_title: Backmarking
caption_attribution_description: The second part of the backmarking example. When the search reaches xi again, part of the assigment is the same as before, and some consistency checks can be avoided.
context_page_description: 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. It improves over backtracking by maintaining information about the last time a variable was instantiated to a value and information about what changed since then. In particular:
  for each variable and value, the algorithm records information about the last time has been set to; in particular, it stores the minimal index such that the assignment to was then inconsistent;
  for each variable, the algorithm stores some information relative to what changed since the last time it has evaluated; in particular, it stores the minimal index of a variable that was changed since then.
  The first information is collected and stored every time the algorithm evaluates a variable to, and is done by simply checking consistency of the current assignments for, for, for, 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 " is possibly changed every time another variable changes value.
context_section_description: 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, . It improves over backtracking by maintaining information about the last time a variable  was instantiated to a value and information about what changed since then. In particular:
  for each variable  and value , the algorithm records information about the last time  has been set to ; in particular, it stores the minimal index  such that the assignment to  was then inconsistent;
  for each variable , the algorithm stores some information relative to what changed since the last time it has evaluated ; in particular, it stores the minimal index  of a variable that was changed since then.
  The first information is collected and stored every time the algorithm evaluates a variable  to , and is done by simply checking consistency of the current assignments for , for , for , 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 " is possibly changed every time another variable  changes value. Every time an arbitrary variable  changes, all variables  with  are considered in turn. If  was their previous associated index, this value is changed to .
  The data collected this way is used to avoid some consistency checks. In particular, whenever backtracking would set , backmarking compares the two indexes relative to  and the pair . Two conditions allow to determine partial consistency or inconsistency without checking with the constraints. If  is the minimal index of a variable that changed since the last time  was evaluated and  is the minimal index such that the evaluation of  was consistent the last time  has been evaluated to , then:
  if , the evaluation of  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 , the evaluation  is still consistent as it was before; this allows for skipping some consistency checks, but the assignment  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.
caption: When search reaches xi=d for the second time, part of the path is the same as the first time.
exif: {}