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: 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