Backtracking

Backtracking is a strategy for finding solutions to problems used in programming languages like Prolog and other areas such as text parsing. Essentially, the idea is to try each possibility until you get the right one. It is a search of the set of solutions.

During the search, if you try an alternative that doesn't work, you backtrack to the choice point, the place which presented you with different alternatives, and you try the next alternative. When you have exhausted the alternatives, you return to the previous choice point and try the next alternative there. If there are no more choice points, the search fails.