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)