The General Pattern

Learn about common backtracking patterns, such as the implicit tree and explicit tree.

Characteristics of backtracking algorithms

Backtracking algorithms are commonly used to make a sequence of decisions, with the goal of building a recursively defined structure satisfying certain constraints. Often (but not always), this goal structure is itself a sequence. For example:

  • In the nn queens problem, the goal is a sequence of queen positions, one in each row, such that no two queens attack each other. For each row, the algorithm decides where to place the queen.
...