backtracking

A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.

In more detail

It explores a decision tree depth-first: choose, recurse, then undo and try the next option. Pruning cuts off hopeless branches early, which is where all its speed comes from. It is the right tool when you need every valid solution, as in N-queens, sudoku or generating permutations.

Related terms

Taught in

References