Backtracking
= Backtracking
Build a candidate incrementally, abandoning a partial candidate as soon as no valid completion is possible. A <depth-first search> explores one choice, restores the previous state, and tries the next. Constraint propagation and bounds can greatly reduce the visited <state space>, although the worst-case <time complexity> may remain exponential.