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, . 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: 1. * 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; 2. * 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: 1. * 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; 2. * 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. (Wikipedia).
