Backtracking
Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.
Fabulous Adventures in Data Structures and Algorithms
A backtracking search algorithm incrementally explores candidate choices and reverses choices that cannot lead to a valid solution.
- How it is used
- Solves constrained graph coloring by exploring candidate assignments and rejecting branches that cannot become solutions.
- How deep it goes
- Builds a general reducer-and-backtracker design in C# and discusses pruning and exponential worst-case behavior.
- Examples
- Works through Sudoku as an 81-node coloring problem and two unconnected nodes yielding 16 colorings.
- What you can do after
- Builds a general backtracker from scratch using a reducer and applies it to graph coloring and Sudoku.
Read how Fabulous Adventures in Data Structures and Algorithms explains backtracking →
Algorithms Every Programmer Should Know
Search backtracking returns to an earlier search state after exploring one branch so that other branches can be examined.
- How it is used
- Uses backtracking to explore alternative clique-building branches and contrasts it with costly pointer resets in naive string search.
- How deep it goes
- Traces recursive state changes and reporting rules for maximal cliques, but treats string-search backtracking chiefly as a bottleneck.
- Examples
- Traces clique branches {1, 2, 4} and {2, 3, 5}, alongside the repetitive-pattern search for AAAAAB.
- What you can do after
- Build it from scratch as a recursive Python maximal-clique search that filters candidates and avoids reporting previously explored cliques.
Read how Algorithms Every Programmer Should Know explains backtracking →
Object-Oriented Software Design in C++
A backtracking technique that recursively explores alternative solution paths and reverses choices when a path fails.
- How it is used
- Applies recursive search when each step offers several possible paths and failures must redirect exploration.
- How deep it goes
- Explains base cases, recursive subproblems, choice reversal, and path exhaustion, while warning that misuse can cause performance problems.
- Examples
- Demonstrates candidate replacement in Sudoku and queen placement, removal, and repositioning in the eight queens puzzle.
- What you can do after
- Apply it via recursive search to solve constraint problems with multiple candidate paths and recover from failed choices.
Read how Object-Oriented Software Design in C++ explains backtracking →
Software Design for Python Programmers
Backtracking is the process of reversing or revising earlier decisions when they lead to an unsatisfactory result.
- How it is used
- Uses iterative revision to recover from poor design decisions and recursive search to explore multiple candidate solution paths.
- How deep it goes
- Explains stages, paths, base cases, choice reversal, and solution termination, then demonstrates the mechanics in complete Python examples.
- Examples
- Demonstrates backtracking through the eight queens puzzle, Sudoku solving, decision trees, and evolving a book catalogue design.
- What you can do after
- Build recursive searches that test valid choices, undo failed choices, and either find one solution or enumerate all solutions.
Read how Software Design for Python Programmers explains backtracking →
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
Backtracking search explores candidate solutions incrementally and reverses decisions when a partial candidate cannot lead to a solution.
- How it is used
- Solves constraint-satisfaction problems and enumerates candidate routes or permutations.
- How deep it goes
- Explains recursive state, variable selection, consistency checks, and restoration, while deferring performance heuristics beyond the simple search.
- Examples
- Demonstrates meeting scheduling, generic constraint frameworks, array permutations, and five-city Vermont routes.
- What you can do after
- Build it from scratch with Swift functions and generic types for constraint solving, permutation generation, and route evaluation.
Optimization Algorithms: AI techniques for design, planning, and control problems
A search technique that returns to an earlier decision point after reaching a dead end and tries another alternative.
- How it is used
- Uses recursive or stack-based search to explore routes, puzzle states, and constraint assignments while recovering from failed choices.
- How deep it goes
- Explains branch exploration, dead-end recovery, stacks, depth bounds, and constraint violations, but does not develop formal complexity theory.
- Examples
- Demonstrates backtracking with the 8-puzzle, path planning, and 9 × 9 Sudoku puzzles.
- What you can do after
- Build it from scratch as a depth-first search using a stack or recursion, explored-state checks, branch alternatives, and termination tests.
Secrets of the JavaScript Ninja, Third Edition
Regex backtracking is a matching strategy that revisits earlier choices to try alternative paths when later matching fails.
- How it is used
- Explains how greedy regex matches recover from later failures and why some failures become performance hazards.
- How deep it goes
- Works through character-by-character retries and a timed catastrophic case, without specifying a particular engine implementation.
- Examples
- Uses a number-and-word pattern matching "27 dresses" and a timed roster regex rejecting an attack string.
- What you can do after
- Diagnose/debug with it when a greedy regex matches unexpectedly or takes too long to reject input.
Read how Secrets of the JavaScript Ninja, Third Edition explains backtracking →
Advanced Algorithms and Data Structures
Backtracking is a technique that reverses or revisits decisions along a path when processing cannot be completed from the current choice.
- How it is used
- Uses reverse traversal to recover trie prefixes and propagate structural repairs through tree insertion paths.
- How deep it goes
- Explains recursive descent, unwinding, fallback checks, ancestor updates, node splits, and stopping conditions.
- Examples
- Demonstrates longest-prefix lookup and SS-tree insertion after a full leaf requires recursive ancestor splitting.
- What you can do after
- Implement recursive trie lookup and tree insertion routines that propagate results or structural changes toward the root.
Read how Advanced Algorithms and Data Structures explains backtracking →
Timeless Algorithms, The Foundational Ideas
Backtracking is a technique that reconstructs a solution by tracing stored decisions backward from a final state.
- How it is used
- Recovers the item choices behind an optimal value after forward tabulation completes.
- How deep it goes
- Defines state comparisons, inclusion and exclusion decisions, capacity updates, and the stopping condition; notes alternative optima on ties.
- Examples
- Traces a capacity-seven knapsack with four items to the optimal set of Items 2, 3, and 4.
- What you can do after
- Understand which decisions produced an optimal value by tracing a completed table backward.
Read how Timeless Algorithms, The Foundational Ideas explains backtracking →
Also covered in
What to know first
- depth-first searchDepth-first search is a traversal strategy that follows a branch as far as possible before backtracking to explore alternatives.
- graphA graph is a mathematical structure consisting of vertices and edges that connect pairs of vertices to represent relationships or connections.
- nodeA node is a discrete element of a graph, tree, linked structure, network, or computing system that can represent an entity, state, or component and may connect to other elements.
Related concepts
- algorithmkind of · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
- Bron–Kerbosch algorithmused by · The Bron–Kerbosch algorithm is a recursive backtracking algorithm for enumerating the maximal cliques of an undirected graph.
- depth-first searchused by · Depth-first search is a traversal strategy that follows a branch as far as possible before backtracking to explore alternatives.
- Knuth-Morris-Pratt algorithmaddressed by · The Knuth-Morris-Pratt algorithm is a string-search procedure that avoids rechecking previously matched text characters by using information about the pattern's prefixes and suffixes.
- recursionused by · Recursion is a computational technique in which a definition or procedure refers to or invokes itself, directly or indirectly.
- Sudoku puzzleaddresses · A Sudoku puzzle is a number-placement constraint puzzle in which each row, column, and designated region contains each permitted symbol exactly once.
Questions about backtracking
What is backtracking?
Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.
Which Manning books explain backtracking?
Fabulous Adventures in Data Structures and Algorithms, Algorithms Every Programmer Should Know, Object-Oriented Software Design in C++, Software Design for Python Programmers, Classic Computer Science Problems in Swift: Essential techniques for practicing programmers, Optimization Algorithms: AI techniques for design, planning, and control problems, Secrets of the JavaScript Ninja, Third Edition, Advanced Algorithms and Data Structures and 1 more.
What should I know before learning backtracking?
Manning books that teach backtracking usually introduce depth-first search, graph, node and chessboard first.
What is backtracking a kind of?
Backtracking is a kind of algorithm. An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
What is backtracking also called?
Backtracking is also called backtrack.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.








