backtracking

    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)