Backtracking Algorithm
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem , that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution. Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates , since it can eliminate a large number of candidates with a single test. Backtracking is an important tool for solving constraint satisfaction problems , such as crosswords , verbal arithmetic , Sudoku , and many other pu...