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 →
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.
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 →
Related concepts
- algorithmkind of · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
- depth-first searchused by · Depth-first search is a graph or tree traversal algorithm that explores one branch as far as possible before backtracking to explore alternatives.
- 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.
- recursionused by · Recursion is a computational technique in which a definition or procedure refers to or invokes the same definition or procedure, directly or indirectly.
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.