BACKTRACKING
\bˈaktɹakɪŋ], \bˈaktɹakɪŋ], \b_ˈa_k_t_ɹ_a_k_ɪ_ŋ]\
Sort: Oldest first

A scheme for solving a series of subproblems eachof which may have multiple possible solutions and where thesolution chosen for one subproblem may affect the possiblesolutions of later subproblems.To solve the overall problem, we find a solution to the firstsubproblem and then attempt to recursively solve the othersubproblems based on this first solution. If we cannot, orwe want all possible solutions, we backtrack and try the nextpossible solution to the first subproblem and so on.Backtracking terminates when there are no more solutions tothe first subproblem.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 subproblems and onlyresolves those which depend on an earlier solution which haschanged.Backtracking is one algorithm which can be used to implementnondeterminism. It is effectively a depthfirst search ofa problem space.
By Denis Howe