Hubbry Logo
logo
Backtracking avatar
Backtracking
Community hub

Backtracking

logo
0 subscribers
Read side by side
Backtracking
View on Wikipedia
from Wikipedia

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 ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.[1]

The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned.

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 many candidates with a single test.

Backtracking is an important tool for solving constraint satisfaction problems,[2] such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient technique for parsing,[3] for the knapsack problem and other combinatorial optimization problems. It is also the program execution strategy used in the programming languages Icon, Planner and Prolog.

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.

The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s.[4] The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility.

Description of the method

[edit]

The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.

Conceptually, the partial candidates are represented as the nodes of a tree structure, the potential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further.

The backtracking algorithm traverses this search tree recursively, from the root down, in depth-first order. At each node c, the algorithm checks whether c can be completed to a valid solution. If it cannot, the whole sub-tree rooted at c is skipped (pruned). Otherwise, the algorithm (1) checks whether c itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all sub-trees of c. The two tests and the children of each node are defined by user-given procedures.

Therefore, the actual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test.

Pseudocode

[edit]

In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:

  1. root(P): return the partial candidate at the root of the search tree.
  2. reject(P,c): return true only if the partial candidate c is not worth completing.
  3. accept(P,c): return true if c is a solution of P, and false otherwise.
  4. first(P,c): generate the first extension of candidate c.
  5. next(P,s): generate the next alternative extension of a candidate, after the extension s.
  6. output(P,c): use the solution c of P, as appropriate to the application.

The backtracking algorithm reduces the problem to the call backtrack(P, root(P)), where backtrack is the following recursive procedure: 

procedure backtrack(P, c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(P, s)
        s ← next(P, s)

Usage considerations

[edit]

The reject procedure should be a Boolean-valued function that returns true only if it is certain that no possible extension of c is a valid solution for P. If the procedure cannot reach a definite conclusion, it should return false. An incorrect true result may cause the backtrack procedure to miss some valid solutions. The procedure may assume that reject(P,t) returned false for every ancestor t of c in the search tree.

On the other hand, the efficiency of the backtracking algorithm depends on reject returning true for candidates that are as close to the root as possible. If reject always returns false, the algorithm will still find all solutions, but it will be equivalent to a brute-force search.

The accept procedure should return true if c is a complete and valid solution for the problem instance P, and false otherwise. It may assume that the partial candidate c and all its ancestors in the tree have passed the reject test.

The general pseudo-code above does not assume that the valid solutions are always leaves of the potential search tree. In other words, it admits the possibility that a valid solution for P can be further extended to yield other valid solutions.

The first and next procedures are used by the backtracking algorithm to enumerate the children of a node c of the tree, that is, the candidates that differ from c by a single extension step. The call first(P,c) should yield the first child of c, in some order; and the call next(P,s) should return the next sibling of node s, in that order. Both functions should return a distinctive "NULL" candidate, if the requested child does not exist.

Together, the root, first, and next functions define the set of partial candidates and the potential search tree. They should be chosen so that every solution of P occurs somewhere in the tree, and no partial candidate occurs more than once. Moreover, they should admit an efficient and effective reject predicate.

Early stopping variants

[edit]

The pseudo-code above will call output for all candidates that are a solution to the given instance P. The algorithm can be modified to stop after finding the first solution, or a specified number of solutions; or after testing a specified number of partial candidates, or after spending a given amount of CPU time.

Examples

[edit]
A Sudoku solved by backtracking

Examples where backtracking can be used to solve puzzles or problems include:

The following is an example where backtracking is used for the constraint satisfaction problem:

Constraint satisfaction

[edit]

The general constraint satisfaction problem consists in finding a list of integers x = (x[1], x[2], …, x[n]), each in some range {1, 2, …, m}, that satisfies some arbitrary constraint (Boolean function) F.

For this class of problems, the instance data P would be the integers m and n, and the predicate F. In a typical backtracking solution to this problem, one could define a partial candidate as a list of integers c = (c[1], c[2], …, c[k]), for any k between 0 and n, that are to be assigned to the first k variables x[1], x[2], …, x[k]. The root candidate would then be the empty list (). The first and next procedures would then be 

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], ..., c[k], 1)

function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], ..., s[k − 1], 1 + s[k])

Here length(c) is the number of elements in the list c.

The call reject(P, c) should return true if the constraint F cannot be satisfied by any list of n integers that begins with the k elements of c. For backtracking to be effective, there must be a way to detect this situation, at least for some candidates c, without enumerating all those mn − k n-tuples.

For example, if F is the conjunction of several Boolean predicates, F = F[1] ∧ F[2] ∧ … ∧ F[p], and each F[i] depends only on a small subset of the variables x[1], …, x[n], then the reject procedure could simply check the terms F[i] that depend only on variables x[1], …, x[k], and return true if any of those terms returns false. In fact, reject needs only check those terms that do depend on x[k], since the terms that depend only on x[1], …, x[k − 1] will have been tested further up in the search tree.

Assuming that reject is implemented as above, then accept(P, c) needs only check whether c is complete, that is, whether it has n elements.

It is generally better to order the list of variables so that it begins with the most critical ones (i.e. the ones with fewest value options, or which have a greater impact on subsequent choices).

One could also allow the next function to choose which variable should be assigned when extending a partial candidate, based on the values of the variables already assigned by it. Further improvements can be obtained by the technique of constraint propagation.

In addition to retaining minimal recovery values used in backing up, backtracking implementations commonly keep a variable trail, to record value change history. An efficient implementation will avoid creating a variable trail entry between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation.

An alternative to the variable trail is to keep a timestamp of when the last change was made to the variable. The timestamp is compared to the timestamp of a choice point. If the choice point has an associated time later than that of the variable, it is unnecessary to revert the variable when the choice point is backtracked, as it was changed before the choice point occurred.

See also

[edit]

Notes

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Backtracking

View on Grokipedia
from Grokipedia
Backtracking is an algorithmic technique in computer science for solving computational problems by incrementally constructing candidate solutions and abandoning partial candidates—known as "backtracking"—as soon as it is determined that they cannot be completed to a valid full solution.[1] This method systematically explores the solution space, often modeled as a tree of decisions, using a depth-first search approach to evaluate alternatives recursively.[2] It is particularly effective for constraint satisfaction problems, where solutions must satisfy a set of constraints, and relies on pruning infeasible branches to improve efficiency over exhaustive enumeration.[3] The core mechanism of backtracking involves representing partial solutions as vectors or sequences, where each position corresponds to a decision variable chosen from a finite domain.[2] A generic recursive procedure, such as Backtrack(a, k), extends the partial solution by selecting the next element, checks for validity or completeness, and either proceeds deeper or backtracks to try alternatives if a dead end is reached.[3] This ensures completeness by eventually enumerating all feasible configurations, though runtime can be exponential in the worst case without effective pruning heuristics like constraint propagation or variable ordering.[1] Backtracking algorithms are often customized for specific problems, incorporating domain-specific tests to reject invalid partial solutions early.[2] Common applications include solving the N-Queens puzzle, where queens must be placed on an N×N chessboard without attacking each other—a problem first posed in 1848 by Max Bezzel and analyzed by Carl Friedrich Gauss in 1850.[1] Other notable uses are in Sudoku solvers, subset sum problems, permutation generation, and graph coloring, demonstrating its versatility in combinatorial search and optimization tasks.[3] Historically, backtracking traces roots to early 20th-century work on game tree search, such as Ernst Zermelo's 1913 strategy for chess, which employed similar recursive enumeration principles.[1]

Fundamentals

Definition and Principles

Backtracking is a depth-first search algorithm employed to solve combinatorial optimization and decision problems by systematically exploring the solution space through incremental construction of candidate solutions. It operates by building partial solutions step by step, testing each extension for validity against problem constraints, and abandoning (backtracking from) any partial path that leads to a violation, thereby reverting to the most recent viable state to explore alternative branches. This approach ensures an exhaustive yet pruned enumeration of possibilities, making it particularly effective for constraint satisfaction problems where the search space is vast but structured.[1][4] The core principles of backtracking revolve around three interconnected mechanisms: incremental construction of candidates, validity checking at each step, and recursive exploration of branches. In incremental construction, the algorithm advances by adding one element at a time to the current partial solution, such as assigning a value to a variable in sequence. Validity checking evaluates whether the new extension satisfies all relevant constraints relative to prior choices, preventing the propagation of invalid configurations. Recursion facilitates the depth-first traversal, allowing the algorithm to delve deeper into promising paths while maintaining the ability to retreat upon failure, thus embodying a trial-and-error paradigm that systematically covers the feasible solution space.[5][1][4] The solution space in backtracking is conceptualized as a tree, where the root represents the empty partial solution, internal nodes denote intermediate partial solutions, and leaves correspond to complete solutions or dead ends. Edges in this tree illustrate the choices made at each step, with backtracking occurring when a subtree rooted at a dead-end node—due to exhaustive exploration yielding no valid extension—is pruned, and the search retreats to an ancestor node to try untried branches. This tree structure highlights the algorithm's efficiency in avoiding redundant computations by not revisiting pruned subtrees.[1][5] Key terminology in backtracking includes partial solution, which refers to an incomplete candidate built up to a certain depth in the search tree; constraint violation, indicating a failure in consistency checks that renders a partial solution invalid and triggers backtracking; and exhaustive search with pruning, describing the method's complete coverage of the solution space tempered by early abandonment of infeasible paths to mitigate computational expense. These concepts underscore backtracking's balance between thoroughness and optimization in navigating complex combinatorial landscapes.[4][1]

Historical Context

The origins of backtracking as an algorithmic technique trace back to the 1950s, when American mathematician D. H. Lehmer coined the term "backtrack" to describe a systematic method for exploring solution spaces in computational problems, particularly in the context of combinatorial enumeration on early computers like the SWAC.[6] This approach was initially applied to problems such as generating permutations and solving puzzles, building on earlier manual methods for maze navigation and puzzle-solving that resembled depth-first search with reversal. Early roots also appeared in work on constraint satisfaction and automated theorem proving, where J. A. Robinson's 1965 resolution principle provided a foundational framework for logical inference through refutation, with implementations relying on search procedures that incrementally built proofs while retracting invalid paths—precursors to modern backtracking in logic-based systems.[7] In the 1960s, backtracking gained its first formal algorithmic description in full generality from R. J. Walker, who used it to solve the n-queens problem for board sizes between 6 and 13, demonstrating its efficiency for enumerative combinatorics.[6] A seminal contribution came from Solomon W. Golomb and Leonard D. Baumert in their 1965 paper, which formalized backtracking as a programmable technique for generating sequences and solving discrete optimization problems, emphasizing its role in avoiding exhaustive enumeration by pruning invalid branches early.[8] Golomb, known for his work on polyomino puzzles since the early 1950s, applied these ideas to tiling problems, highlighting backtracking's utility in recreational mathematics and early computer applications.[8] By the 1970s, backtracking was further refined in papers on combinatorial search, such as Bitner and Reingold's 1975 exposition, which detailed its general structure and applications to parsing and optimization, solidifying it as a core paradigm in algorithm design.[6] The 1980s saw its integration into artificial intelligence and operations research, particularly in expert systems where chronological backtracking managed rule-based inference and error tracing in domains like configuration tasks.[9] This era also featured its embedding in programming languages like Prolog, developed by Alain Colmerauer and Philippe Roussel in 1972, where backtracking became the engine for depth-first execution of logic programs, enabling declarative solving of constraint problems in AI applications.[10] The evolution continued into the 2000s with adaptations for parallel computing on multicore systems, where variants distributed search trees across processors to accelerate enumeration while preserving sequential semantics through techniques like distributed backtracking.[11]

Algorithm Implementation

Core Pseudocode

The backtracking algorithm follows a standard recursive template that incrementally constructs candidate solutions, checks constraints at each step, and abandons partial solutions that cannot lead to valid outcomes. This generalized structure, often presented in academic literature on algorithmic design, operates by maintaining a partial solution and exploring possible extensions depth-first.[1] A typical implementation uses a recursive function, such as backtrack(partial_solution, current_position), which first checks base cases: if the partial solution is complete, it validates and returns it as a success; if no candidates remain at the current position, it returns failure. Otherwise, it generates possible candidates via a choice function, adds each valid one to the partial solution after constraint checking, recurses to the next position, and removes (backtracks) the choice upon failure or completion of exploration. Key components include the choice function, which enumerates feasible options (e.g., unused elements); the constraint checker, which ensures partial consistency; and the solution validator, which confirms full solutions against problem-specific criteria. This framework enables systematic enumeration while avoiding exhaustive search through early abandonment.[1] The following pseudocode outlines this generic recursive structure: 
function backtrack(partial_solution, current_position):
    if is_complete(partial_solution):
        if is_valid_solution(partial_solution):
            return partial_solution  // Success: report or store solution
        else:
            return failure  // Invalid full solution
    if no_candidates_available(current_position):
        return failure  // No way to proceed
    
    for each candidate in choices(current_position, partial_solution):
        if constraint_satisfied(candidate, partial_solution):
            add_to_solution(partial_solution, candidate, current_position)
            result = backtrack(partial_solution, current_position + 1)
            if result != failure:
                return result  // Propagate success
            remove_from_solution(partial_solution, current_position)  // Backtrack
    return failure  // All branches exhausted
This template is adaptable to various problems by customizing the choice, constraint, and validation functions.[1] As an illustrative example, consider generating all permutations of a set of nn distinct elements using backtracking, a classic application that demonstrates the template without additional constraints beyond uniqueness. The algorithm builds the permutation position by position, selecting unused elements as candidates. Base cases occur when the permutation reaches length nn (success, process the solution) or no unused elements remain prematurely (failure, though unlikely in this unconstrained case). The choice function identifies available elements not yet in the partial permutation.[2] Pseudocode for permutation generation, adapted from standard algorithmic lectures, uses an array a to store the partial permutation, with index k tracking the current position (starting from 0) and n as the set size: 
function backtrack(a, k, n):
    if k == n:
        process_solution(a)  // e.g., print or store the permutation
        return
    candidates = construct_candidates(a, k, n)
    for i = 0 to length(candidates) - 1:
        a[k] = candidates[i]
        backtrack(a, k + 1, n)
        // No explicit removal needed if overwriting in next iteration

function construct_candidates(a, k, n):
    used = [empty set](/page/Empty_set)
    for i = 0 to k - 1:
        add a[i] to used
    return [element for element in 1 to n if element not in used]
This approach generates permutations in a depth-first manner, ensuring each is unique by excluding used elements, and can be initialized by calling backtrack([empty_array](/page/Array), 0, n). For efficiency, the construct_candidates step typically uses a boolean array to track usage, avoiding repeated scans.[2]

Execution Process

The backtracking algorithm executes as a depth-first search through a space of possible solutions, incrementally constructing candidate solutions by making choices at each decision point and retracting them—known as backtracking—when a choice leads to an invalid partial solution or a dead end. This process systematically explores all feasible paths until complete solutions are found or the entire search space is exhausted. The dynamic nature of execution relies on recursion to manage the exploration, where each recursive call represents advancing deeper into the search tree by trying a candidate, and returning from the call simulates the backtrack by undoing the trial. To illustrate, consider the basic problem of generating all subsets of the set {1, 2, 3}, which produces 2^3 = 8 subsets without any constraints failing the process. The algorithm begins at the root of the search tree with an empty partial solution and index i=0, corresponding to the first element. It recursively decides to either include or exclude each element, advancing the index until i reaches 3, at which point the current partial solution is recorded as a complete subset before backtracking. For instance:
  • Start: empty subset, i=0.
    • Include 1 (add 1 to partial: {1}), recurse with i=1.
      • Include 2 (partial: {1,2}), i=2.
        • Include 3 (partial: {1,2,3}), i=3 → record {1,2,3}, backtrack (remove 3).
        • Exclude 3 (partial: {1,2}), i=3 → record {1,2}, backtrack (remove 2).
      • Exclude 2 (partial: {1}), i=2.
        • Include 3 (partial: {1,3}), i=3 → record {1,3}, backtrack (remove 3).
        • Exclude 3 (partial: {1}), i=3 → record {1}, backtrack (remove 1).
    • Exclude 1 (partial: empty), i=1.
      • Include 2 (partial: {2}), i=2.
        • Include 3 (partial: {2,3}), i=3 → record {2,3}, backtrack.
        • Exclude 3 (partial: {2}), i=3 → record {2}, backtrack.
      • Exclude 2 (partial: empty), i=2.
        • Include 3 (partial: {3}), i=3 → record {3}, backtrack.
        • Exclude 3 (partial: empty), i=3 → record {}, backtrack.
This textual trace depicts the search tree, where forward progress occurs via recursive calls (indenting deeper levels), and back jumps happen upon returning (popping up levels after exploring a branch). In cases with constraints, such as subset sum targeting a specific value, a failure check after adding a candidate would trigger immediate backtracking without recording, pruning invalid paths early.[1][12] State management during execution involves maintaining a mutable partial solution, typically as a dynamic array or list, to track the current path's choices. When trying a candidate, the algorithm adds it to the partial solution and proceeds recursively; upon backtracking, it removes (or "unchooses") the last addition to restore the state for sibling branches. This undo mechanism ensures that each recursive branch starts from the correct prefix without redundant copying, preserving efficiency in exploring alternatives. For example, in the subset generation above, adding 1 modifies the array to include it, but removing it after the {1}-prefixed branches allows clean exploration of subsets excluding 1.[1][12] The recursion stack plays a crucial role in tracking the current path and facilitating backtracking, as each active recursive call corresponds to a node in the search tree, holding local state like the current index and partial solution reference. When a leaf is reached (base case, e.g., i == n), the solution is processed, and returns propagate up the stack, automatically reverting changes as frames unwind. This stack-based structure enables depth-first traversal without explicit tree storage, making backtracking memory-efficient for deep search spaces while naturally handling the reversal of decisions. As referenced in the core pseudocode template, the recursive function advances by calling itself with updated parameters after choice trials.[1][12]

Optimizations and Variants

Pruning Techniques

Pruning techniques in backtracking algorithms aim to eliminate portions of the search tree that cannot lead to a valid solution, thereby reducing computational overhead without sacrificing completeness. These methods leverage constraint propagation and intelligent selection strategies to detect inconsistencies early, minimizing the exploration of unpromising branches. By integrating such techniques, backtracking becomes more efficient for solving constraint satisfaction problems (CSPs), particularly those with tight constraints and large domains.[13] Forward checking is a foundational pruning method that propagates constraints from assigned variables to unassigned ones during the search process. Upon assigning a value to a variable, forward checking removes any inconsistent values from the domains of future variables connected by binary constraints, potentially detecting dead-ends immediately if a domain becomes empty. This approach, introduced as an enhancement to basic backtracking, significantly prunes the search tree by avoiding assignments that would inevitably fail later. For instance, in a graph coloring problem, assigning a color to one node would eliminate that color from adjacent uncolored nodes' domains.[13] Arc consistency enforcement extends forward checking by maintaining a stronger level of consistency across the constraint network throughout the backtracking search. Known as Maintaining Arc Consistency (MAC), this technique repeatedly applies arc consistency algorithms, such as AC-3, after each variable assignment to reduce domains of all unassigned variables, ensuring that every value in a domain has at least one compatible value in neighboring domains. Unlike forward checking, which only checks future variables directly constrained by the current one, MAC considers indirect effects, leading to more aggressive pruning but at higher computational cost per node. Empirical evaluations show MAC outperforming forward checking on structured CSPs by detecting failures deeper in the search tree. Lookahead strategies further refine pruning by assessing the potential impact of partial assignments on the remaining search space before committing to a branch. These include partial lookahead, which checks consistency for a limited set of future variables, and full lookahead, which evaluates the entire unassigned subproblem for consistency after an assignment. By simulating constraint propagation one or more steps ahead, lookahead identifies and prunes branches where no complete solution exists, balancing the trade-off between pruning effectiveness and overhead. In practice, lookahead is most beneficial in domains with high constraint density, where it can reduce the effective branching factor substantially.[13] Heuristic ordering enhances pruning by guiding the selection of variables and values to prioritize branches likely to fail early, thereby exposing inconsistencies sooner. The most constrained variable (MCV) heuristic, also called minimum remaining values (MRV), selects the unassigned variable with the smallest current domain, as it is most likely to cause failure. Complementing this, the least constraining value (LCV) heuristic chooses values that impose the fewest restrictions on future variables, measured by the number of surviving values in affected domains after assignment. These static and dynamic ordering heuristics, when combined with propagation, can reduce the search tree size exponentially in many CSP benchmarks.[13] In optimization contexts, backtracking can adapt alpha-beta-like pruning through branch-and-bound methods, where lower and upper bounds on objective functions guide the elimination of suboptimal branches. Upon exploring a partial solution, if its bound indicates it cannot improve the current best solution, the entire subtree is pruned, mirroring alpha-beta's cutoff in minimax trees. This adaptation, originating in discrete programming, extends backtracking to find optimal solutions efficiently by integrating bounding functions with constraint propagation. For example, in integer linear programming, relaxations provide bounds to prune non-improving paths early.[14]

Early Termination Methods

In backtracking algorithms applied to decision problems, such as determining whether a solution exists in a constraint satisfaction problem (CSP), the search terminates immediately upon finding the first valid solution, avoiding unnecessary exploration of the remaining search space.[1] In contrast, for problems requiring enumeration of all solutions or counting them, such as generating all possible configurations in a puzzle, the algorithm continues the exhaustive search until the entire tree is traversed, reporting or accumulating all valid outcomes.[1] For optimization variants of backtracking, bounding techniques enable early termination of partial solutions that cannot improve upon a known incumbent solution. In branch-and-bound methods integrated with backtracking, an upper or lower bound is computed for each partial assignment; if this bound indicates that the subtree rooted at the current node cannot yield a better solution than the current best, the search prunes that branch entirely. This approach, originally formalized for discrete programming problems, significantly reduces the effective search space in applications like the traveling salesman problem by dynamically updating bounds during the depth-first traversal. Symmetry breaking methods in backtracking prevent redundant exploration of isomorphic subtrees by enforcing a canonical ordering on variable assignments or values, thereby terminating symmetric branches early. One prominent technique adds conditional constraints during search to break remaining symmetries upon backtracking, ensuring that only distinct representatives of equivalent solutions are pursued.[15] For instance, in graph coloring problems with automorphism symmetries, ordering variables by labels or values eliminates duplicate searches, as demonstrated in improvements to symmetry-breaking during search (SBDS) that dynamically post constraints to avoid symmetric failures.[16] Backtracking can integrate with iterative deepening to impose depth limits, terminating paths that exceed a current threshold and restarting with incrementally larger limits until a solution is found or futility is confirmed. This hybrid, known as iterative deepening depth-first search (IDDFS), combines the space efficiency of depth-first backtracking with completeness guarantees, particularly useful in unbounded domains where pure backtracking risks infinite descent. By failing and backtracking from deep, unproductive paths within each iteration, it avoids exhaustive exploration at excessive depths while converging on optimal solutions in tree-like search spaces. Detection of unsolvable instances in backtracking occurs through domain wipeout, where constraint propagation empties the domain of an unassigned variable, signaling a dead-end and prompting immediate backtrack or failure declaration. In forward-checking or more advanced propagation schemes, a domain wipeout at any point indicates inconsistency in the partial assignment, allowing the algorithm to terminate the search for that branch without further recursion.[17] This mechanism, central to efficient CSP solvers, enables early recognition of infeasible problems by propagating failures upward, often combined with heuristics to minimize such wipeouts.[17]

Applications

Constraint Satisfaction Problems

A constraint satisfaction problem (CSP) is formally defined as a triple (X,D,C)(X, D, C), where X={X1,…,Xn}X = \{X_1, \dots, X_n\} is a finite set of decision variables, D={D(X1),…,D(Xn)}D = \{D(X_1), \dots, D(X_n)\} assigns a finite domain of possible values to each variable, and CC is a set of constraints that restrict the allowable combinations of values among subsets of variables.[18] Each constraint Ck∈CC_k \in C is a relation over a subset of variables, specifying the tuples that satisfy it, and the goal is to find an assignment of values to all variables such that every constraint is satisfied.[19] This framework captures a wide range of combinatorial problems by modeling them through variable assignments subject to relational restrictions.[18] Backtracking algorithms solve CSPs by exploring the search space of partial assignments in a depth-first manner, building solutions incrementally while pruning inconsistent branches.[19] The process begins by selecting an unassigned variable, trying values from its domain in sequence, and checking whether the partial assignment violates any unary (single-variable) or binary (two-variable) constraints involving the newly assigned variable and previously assigned ones.[20] If no conflict arises, the algorithm recurses to the next variable; otherwise, it backtracks to the last choice point, removes the conflicting value, and tries the next alternative.[19] This systematic enumeration ensures completeness, as it exhaustively explores all possible combinations until a valid solution is found or the search space is proven empty.[20] A classic example is the graph coloring problem, often illustrated as map coloring, where the task is to assign colors to regions such that no adjacent regions share the same color.[21] Backtracking proceeds by assigning a color to a region, checking consistency with neighboring assigned regions, and recursing; if a conflict arises later, it backtracks to try alternative colors. For instance, in a map with mutually adjacent regions forming a cycle, the algorithm may assign colors sequentially, pruning branches where adjacent regions match, until a valid coloring is found or all possibilities are exhausted. For constraints of arity greater than two (n-ary constraints), backtracking generalizes the checking mechanism by evaluating each constraint against the current partial assignment restricted to the variables it involves, ensuring consistency only when all relevant variables are assigned.[19] Unary constraints can be handled by pre-filtering domains, while higher-arity ones are assessed via a constraint-checking function that returns true if the assigned values form an allowable tuple.[20] To improve efficiency before or interleaved with backtracking, preprocessing techniques like arc consistency enforcement via the AC-3 algorithm prune domains by removing values that cannot participate in any complete solution.[22] AC-3 operates by maintaining a queue of directed arcs (Xi,Xj)(X_i, X_j) corresponding to constraints and iteratively revising D(Xi)D(X_i) to retain only values for which there exists a supporting value in D(Xj)D(X_j) that satisfies the constraint C(Xi,Xj)C(X_i, X_j); arcs are requeued if revisions occur, propagating consistency until no changes remain.[22] This local consistency check reduces the effective search space without losing solutions, as demonstrated in binary CSPs where arc consistency alone solves tree-structured problems.[22]

Puzzle Solving Examples

Backtracking algorithms find frequent application in solving combinatorial puzzles, where the search space involves placing or selecting elements under strict constraints. One classic example is the N-Queens problem, which requires placing N queens on an N×N chessboard such that no two queens threaten each other, meaning they share no row, column, or diagonal.[23] The backtracking approach proceeds row by row, attempting to place a queen in each column of the current row while checking for conflicts with previously placed queens. If a placement violates constraints, the algorithm backtracks to the previous row and tries the next column.[24] To illustrate, consider the 4-Queens problem. The algorithm represents the board as an array Q where Q[i] denotes the column for the queen in row i. It systematically tries placements, backtracking on conflicts, until finding a solution such as Q = [2, 4, 1, 3], where no pairs share rows, columns, or diagonals (checked via |Q[i] - Q[j]| ≠ |i - j| for i ≠ j).[23][24] A tailored pseudocode for N-Queens builds on the core backtracking template: 
function PlaceQueens(Q[1..N], r):
    if r == N + 1:
        output solution Q
    else:
        for j = 1 to N:
            if [safe](/page/Safe)(r, j, Q[1..r-1]):  // no conflicts in column or diagonals
                Q[r] = j
                PlaceQueens(Q, r + 1)
                Q[r] = 0  // backtrack
The safe check verifies no prior queen at (r, j) shares a column (Q[k] ≠ j for k < r) or diagonal (|Q[k] - j| ≠ |k - r| for k < r).[23] Another prominent puzzle is Sudoku, a 9×9 grid divided into nine 3×3 subgrids, to be filled with digits 1-9 such that each row, column, and subgrid contains all digits exactly once. Backtracking solves this by selecting an empty cell, trying digits 1-9 in sequence, and verifying compliance with row, column, and subgrid rules before proceeding to the next cell. If a digit leads to a violation later, the algorithm backtracks to the current cell, resets it to empty, and tries the next digit; if no digit works, it backtracks further.[25][26] For a partial trace on a simple unsolved Sudoku (with some cells pre-filled), the algorithm tries values in empty cells, pruning invalid placements early through constraint checks. This depth-first exploration prunes invalid partial grids early, typically achieving solutions efficiently for standard puzzles.[25][26] Pseudocode for a Sudoku solver adapts the backtracking core as follows: 
function SolveSudoku(grid[9][9]):
    find empty cell (i, j)
    if no empty cell:
        return true  // solved
    for num = 1 to 9:
        if isSafe(grid, i, j, num):  // check row, col, 3x3 box
            grid[i][j] = num
            if SolveSudoku(grid):
                return true
            grid[i][j] = 0  // backtrack
    return false
The isSafe function scans the row, column, and subgrid (box starting at floor(i/3)*3, floor(j/3)*3) to ensure num appears nowhere.[26] The subset sum problem exemplifies backtracking in selection-based puzzles: given a set of positive integers X = {x1, ..., xn} and target T, determine if a subset sums exactly to T. The algorithm branches knapsack-style, deciding for each element whether to include or exclude it, recursing on the remaining elements and updated sum, and backtracking on paths exceeding T or failing to reach it.[27][23] In a trace for X = {1, 3, 4, 5}, T = 7: the recursion explores inclusion/exclusion branches, eventually finding {3,4} sums to 7, with the recursion tree exploring up to 2^4 = 16 paths in the worst case.[27] A pseudocode variant for subset sum, recoverable for the actual subset, is: 
function SubsetSum(X[1..n], T):
    if T == 0:
        return true  // empty subset
    if n == 0 or T < 0:
        return false
    // exclude X[n]
    if SubsetSum(X[1..n-1], T):
        return true
    // include X[n]
    if SubsetSum(X[1..n-1], T - X[n]):
        include X[n] in solution
        return true
    return false
This dual-branching ensures exhaustive but pruned search, with time O(2^n).[27][23]

Analysis

Complexity Measures

The time complexity of backtracking algorithms is exponential in the worst case, bounded by $ O(b^d) $, where $ b $ represents the branching factor (the average number of possible choices per decision point) and $ d $ denotes the depth of the search tree, equivalent to the number of variables or decisions required to reach a solution.[28] This bound reflects the potential exploration of the full solution space, as the algorithm systematically tries combinations until constraints are satisfied or exhausted.[20] In the context of constraint satisfaction problems (CSPs), where each of $ n $ variables has a domain of size $ d $, the worst-case time complexity simplifies to $ O(d^n) $.[29] The space complexity of backtracking is more favorable, requiring $ O(d) $ space primarily for the recursion stack that tracks the current partial assignment along the search path.[28] This linear space usage contrasts with the exponential time, making backtracking memory-efficient compared to breadth-first alternatives, though deep recursion can still pose practical limits in implementation.[20] Several factors influence the practical performance of backtracking beyond the worst-case bounds. Constraint tightness, defined as the fraction of incompatible value pairs across constraints, determines the degree of early pruning by restricting invalid branches; tighter constraints enable more aggressive elimination of subtrees, while looser ones expand the search.[30] Larger domain sizes amplify the branching factor, exponentially increasing the explored nodes, whereas effective heuristics—such as minimum remaining values for variable ordering—prioritize promising paths and mitigate this growth.[20] Empirical studies reveal that, despite the inherent exponential growth, pruning mechanisms like forward checking or arc consistency often reduce the effective complexity to polynomial levels for many real-world CSP instances.[20] For example, in the n-queens problem, forward checking combined with heuristics such as search-rearrangement prunes the search space sufficiently to solve instances up to n=96 efficiently, far beyond naive enumeration.[20] Similarly, in polyhedral scene labeling, constraint propagation can eliminate the need for backtracking altogether in some cases.[20] The unpruned search tree size in a CSP is given by the product of the domain sizes, $ \prod_{i=1}^n |D_i| $, representing the total combinatorial possibilities.[31] Pruning subtracts incompatible branches during execution, yielding the actual explored size, which heuristics and propagation aim to minimize toward feasible computation.[20]

Comparisons to Alternatives

Backtracking serves as an efficient refinement over brute-force enumeration, which exhaustively generates and tests all possible combinations without pruning, often leading to infeasible computation times for problems with large search spaces.[32] In contrast, backtracking incrementally builds candidate solutions and abandons partial paths that violate constraints early, significantly reducing the number of explored nodes in exponential search trees while maintaining completeness.[32] This pruning mechanism makes backtracking preferable for constraint satisfaction problems (CSPs) where invalid partial assignments can be detected quickly, avoiding the full traversal required by brute force.[33] Compared to dynamic programming (DP), backtracking lacks memoization and subproblem overlap exploitation, potentially re-exploring similar states and incurring higher time complexity in worst-case scenarios.[32] However, DP typically demands exponential space to store solutions for all subproblems and is better suited for problems requiring all possible solutions or those with optimal substructure, whereas backtracking uses only polynomial space and focuses on finding one feasible solution, making it more practical for large-scale CSPs where proving unsatisfiability is key.[32] Backtracking thus excels in scenarios without heavy overlapping subproblems, such as detecting infeasibility without enumerating everything.[32] Branch and bound shares similarities with backtracking in its tree-search structure and pruning capabilities but emphasizes optimization by using upper or lower bounds to eliminate branches that cannot yield better solutions than the current best.[34] While backtracking prioritizes feasibility in decision problems like CSP satisfiability, branch and bound targets minimization or maximization objectives, often employing depth-first exploration for global optimality.[32] The key trade-off is that backtracking guarantees a solution if one exists without bound computations, but it may explore more nodes in optimization contexts; branch and bound, conversely, can be more efficient for problems with relaxable bounds but requires additional overhead for bound estimation.[35] In opposition to genetic algorithms (GAs), which are population-based metaheuristics providing approximate solutions through evolutionary principles like selection and mutation, backtracking delivers exact, complete results by systematically enumerating the search space.[36] GAs trade completeness for scalability in large, complex optimization landscapes, often converging faster on near-optimal solutions without guarantees, whereas backtracking ensures optimality or feasibility at the cost of potential exponential time in dense domains.[37] This exactness makes backtracking ideal for verification-critical applications, while GAs suit high-dimensional problems where approximations suffice.[36] Backtracking is particularly advantageous in CSPs featuring sparse constraints—where few inter-variable dependencies exist—and small variable domains, as these allow effective early pruning without excessive branching, keeping the search tractable compared to denser alternatives that overwhelm other methods.[32] In such cases, its completeness provides reliable outcomes where approximate techniques like GAs might falter, and its simplicity avoids the space demands of DP or bound computations in branch and bound.[32]

References

  1. [PDF] Backtracking
  2. [PDF] Lecture 15: Backtracking Steven Skiena Department of Computer ...
  3. [PDF] Lecture 3: Backtracking
  4. [PDF] Chapter 5 General search strategies: Look-ahead
  5. [PDF] Chapter 1 RANDOMIZED BACKTRACK SEARCH Extending the ...
  6. https://dl.acm.org/doi/10.1145/361219.361224
  7. A Machine-Oriented Logic Based on the Resolution Principle | Journal of the ACM
  8. Backtrack Programming | Journal of the ACM
  9. [PDF] AN OVERVIEW OF EXPERT SYSTEMS
  10. [PDF] A view of the origins and development of Prolog
  11. [PDF] An implementation of the backtracking algorithm for multicore systems
  12. [PDF] BACKTRACKING - UF CISE
  13. [PDF] Increasing Tree Search Efficiency for Constraint Satisfaction Problems
  14. [PDF] An Automatic Method of Solving Discrete Programming Problems ...
  15. [PDF] Groups and Constraints: Symmetry Breaking during Search
  16. [PDF] Improvements of Symmetry Breaking During Search - IJCAI
  17. [PDF] Chapter 2 Backtracking - UNL School of Computing
  18. [PDF] Networks of Constraints - UNL School of Computing
  19. [PDF] Backtracking algorithms for constraint satisfaction problems
  20. [PDF] Algorithms for Constraint-Satisfaction Problems: A Survey
  21. [PDF] 5 CONSTRAINT SATISFACTION PROBLEMS
  22. [PDF] Consistency in Networks of Relations - UNL School of Computing
  23. [PDF] Backtracking
  24. [PDF] 15–150: Principles of Functional Programming n-Queens
  25. [PDF] A Study Of Sudoku Solving Algorithms: Backtracking and Heuristic
  26. None
  27. [PDF] CS 31: Algorithms (Spring 2019): Lecture 6 1 Subset Sum
  28. [PDF] tree search Backtracking search - CS221 Stanford
  29. [PDF] Artificial Intelligence - UTSC Unit 2 Constraint Satisfaction Problems
  30. [PDF] An Average Analysis of Backtracking on Random Constraint ... - arXiv
  31. Constraint-satisfaction problems (and how to solve them)
  32. [PDF] Backtracking Search Algorithms
  33. [PDF] Algorithms & Models of Computation - Backtracking and Memoization
  34. Difference between Backtracking and Branch-N-Bound technique
  35. Difference between Backtracking and Branch-N-Bound technique
  36. Combining Genetic Algorithm with Local Search Method in Solving ...
  37. Backtracking Search Algorithms - ScienceDirect.com
User Avatar
No comments yet.