Source : Free On-Line Dictionary of Computing

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)