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 languageSSuch aSProlog 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)
