## Definition

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate C ("backtracks") as soon as it determines that C cannot possibly be completed to a valid solution.

This technique has the advantage of being much more efficient a purely exhaustive search.

Source: Wikipedia (license)