Backtracking Algorithm

A Backtracking Algorithm is a search algorithm that incrementally builds solution candidates, and abandons each partial candidate [math]\displaystyle{ c }[/math] ("backtracks") as soon as it determines that [math]\displaystyle{ c }[/math] cannot possibly be completed to a valid solution.

• Context:
  • …
• Example(s):
  • Backtracking Search Algorithm.
  • …
• Counter-Example(s):
  • Intelligent Backtracking,
  • Backjumping Algorithm,
  • Dynamic Backtracking Algorithm,
  • Forward Checking Algorithm,
  • Look Ahead Algorithm,
  • Min-Conflict Algorithm,
  • Generate-and-Test Algorithm.
• See: Constraint Satisfaction Algorithm, Branch and Bound Algorithm, Algorithm Strategy.

---

---

References

2009

• (Wkipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Backtracking
  • 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 [math]\displaystyle{ c }[/math] ("backtracks") as soon as it determines that [math]\displaystyle{ c }[/math] cannot possibly be completed to a valid solution.
  • The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of [math]\displaystyle{ k }[/math] queens in the first [math]\displaystyle{ k }[/math] rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned, since it 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, and many other puzzles. It is often the most convenient (if not the most efficient) technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog. Backtracking is also utilized in the (diff) difference engine for the MediaWiki software.
  • Backtracking depends on user-given “black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm --- although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time.

2008

• (Jones, 2008) ⇒ M. Tim Jones. (2008). “Artificial Intelligence: A Systems Approach." Jones & Bartlett. ISBN:0763773379
  • The backtracking algorithm operates with a simple uninformed search algorithm, such as depth-first search. At each node, a variables is instantiated with a value and the constraint violations are checked. If the values are legal, search is permitted to continue, otherwise, the current branch is abandoned and the next node from the OPEN list is evaluated.

1992

• (Kumar,1992) ⇒ Vipin Kumar (1992). "Algorithms for constraint-satisfaction problems: A survey" (PDF). AI magazine, 13(1), 32.
  • QUOTE: A more efficient method uses the backtracking paradigm. In this method, variables are instantiated sequentially. As soon as all the variables relevant to a constraint are instantiated, the validity of the constraint is checked. If a partial instantiation violates any of the constraints, backtracking is performed to the most recently instantiated variable that still has alternatives available. Clearly, whenever a partial instantiation violates a constraint, backtracking is able to eliminate a subspace from the Cartesian product of all variable domains. The backtracking method essentially performs a depth-first search (Kumar 1987) of the space of potential CSP solutions. Although backtracking is strictly better than the generate-and-test method, its run-time complexity for most nontrivial problems is still exponential. One of the reasons for this poor performance is that the backtracking paradigm suffers from thrashing (Gaschnig 1979); that is, search in different parts of the space keeps failing for the same reasons. The simplest cause of thrashing concerns the unary predicates and is referred to as node inconsistency (Mackworth 1977a).

1976

• Douglas C. Schmidt, and Larry E. Druffel. (1976). “A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices.” In: Journal of the ACM, 23(3). doi:10.1145/321958.321963

---