Build a candidate incrementally, abandoning a partial candidate as soon as no valid completion is possible. A depth-first search explores one choice, restores the previous state, and tries the next. Constraint propagation and bounds can greatly reduce the visited state space, although the worst-case time complexity may remain exponential.
Suppose backtracking assigns each of finitely many variables once along each branch, branching only on distinct values in its initial nonempty constraint domain . Then the number of leaves is at most , even if inconsistent partial assignments terminate early. Ignore constraints and associate a leaf with every full domain assignment extending its partial assignment. Each leaf has at least one such extension. Different leaves have disjoint extension families: at their first diverging choice they assigned different values to the same selected variable. These nonempty disjoint families lie in a Cartesian product of cardinality , proving the bound. The selected next variable can depend on the preceding assignments, provided each full assignment follows a unique branch.
The bound is exact for an unpruned enumeration tree, but need not be attained when actual constraints cause search pruning. Counting complete satisfying assignments alone also does not count failed partial leaves.
Articles by others on the same topic
Backtracking is an algorithmic technique used for solving problems incrementally by trying to build a solution piece by piece and removing those solutions that fail to satisfy the conditions of the problem. It can be viewed as a refined brute-force approach that systematically searches for a solution by exploring and abandoning paths (backtracking) when a solution cannot be obtained. Here are the key characteristics and steps involved in backtracking: 1. **Incremental Construction**: Solutions are built incrementally.