Backtracking explores a space of candidate solutions incrementally and abandons a partial candidate as soon as it cannot lead to a valid complete solution.

A typical search chooses one decision, recursively explores the consequences, then restores the previous state before trying another choice.

choose
explore
undo
try next choice

The search space can often be viewed as a tree whose nodes are partial solutions.

A pruning rule discards branches that violate constraints or cannot improve the best solution found so far. Good pruning can reduce the practical search dramatically, although the worst-case running time may still be exponential.

Backtracking is useful for constraint satisfaction, permutations, puzzles and combinatorial search when no direct constructive algorithm is known.