Dictionary.net

A scheme for solving a series of sub-problems eachof which may have multiple possible solutions and where thesolution chosen for one sub-problem may affect the possiblesolutions of later sub-problems.To solve the overall problem, we find a solution to the firstsub-problem and then attempt to recursively solve the othersub-problems based on this first solution. If we cannot, orwe want all possible solutions, we backtrack and try the nextpossible solution to the first sub-problem and so on.Backtracking terminates when there are no more solutions tothe first sub-problem.This is the algorithm used by logic programming languagessuch as Prolog to find all possible ways of proving agoal. An optimisation known as "intelligent backtracking"keeps track of the dependencies between sub-problems and onlyre-solves those which depend on an earlier solution which haschanged.Backtracking is one algorithm which can be used to implementnondeterminism. It is effectively a depth-first search ofa problem space.