Backtracking

A constraint problem specifies variables, allowed domains and relations they must satisfy. Starting unassigned, backtracking chooses a variable and tries a value, extending a partial assignment until a complete consistent assignment is found.

Depth-first order describes exploration, while backtracking must also track tried choices and restore parent state. Implementations can copy state or undo recorded changes. A failed branch must not leave assignments that corrupt a later alternative.

References: [1]

An already violated constraint cannot be repaired merely by assigning unrelated remaining variables, so the branch can stop early. A chosen variable order also avoids enumerating the same assignment through every possible ordering of decisions.

Forward checking removes values from neighboring unassigned domains when a new assignment makes them incompatible. An empty domain reveals a dead end. Backtracking must restore pruned domains as well as undo the explicit assignment.

References: [1]

Pruning must be sound: deleted branches must truly be unable to produce a required solution. A heuristic for which option to try first differs from a proof that an option may be permanently discarded.

On a finite space, exhaustive exploration retaining necessary branches can find a solution or establish none exists. A timeout generally establishes only that none has yet been found. Local checking and propagation improve many instances without guaranteeing polynomial worst-case time.

References: [1]