Backtracking refers to a scheme for solving a problem by solving a series of constituent sub-problems. Each of the sub-problems has a number of possible solutions, and a solution chosen affects the possible solutions of the remaining sub-problems.

Backtracking algorithms date back to 1965, when Colomb and Baumert published the first algorithm. In 1983, Allen proposed that backtracking could be adapted for use to explore the logical computational solving of problems.

The fact that there can be more than one solution to a computational problem is known as nondeterminism. Backtracking is essential for the operation of a nondeterministic algorithm, that is, solving a problem that can have multiple solutions. Diagramming the possible combinations of sub-problems having multiple, possible solutions produces a tree-like image, with branches representing the possible paths of the various solutions. Thus, backtracking is described as a means of solving problems with tree structures. Negotiating through the tree...