backtracking

algorithm A scheme for solving a series of sub-problems each

of which may have multiple possible solutions and where the

solution chosen for one sub-problem may affect the possible

solutions of later sub-problems.

To solve the overall problem, we find a solution to the first

sub-problem and then attempt to recursively solve the other

sub-problems based on this first solution. If we cannot, or

we want all possible solutions, we backtrack and try the next

possible solution to the first sub-problem and so on.

Backtracking terminates when there are no more solutions to

the first sub-problem.

This is the algorithm used by logic programming languages

such as Prolog to find all possible ways of proving a

goal. An optimisation known as "intelligent backtracking"

keeps track of the dependencies between sub-problems and only

re-solves those which depend on an earlier solution which has

changed.

Backtracking is one algorithm which can be used to implement

nondeterminism. It is effectively a depth-first search of

a problem space.

(1995-04-13)