Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction or enumeration problems, that incrementally builds candidates to the solutions and abandons a candidate as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example is the eight queens puzzle, which asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other; the partial candidates are arrangements of k queens in the first k rows, and any partial solution that contains two mutually attacking queens can be abandoned. Backtracking can be applied only to problems that admit the concept of a partial candidate solution. Algorithms recorded in this atlas are grouped here when their design technique is backtracking.