liveBook · Manning

Backtracking

Also called backtrack

Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.

How 9 Manning books explain it

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.

Read how Classic Computer Science Problems in Swift: Essential techniques for practicing programmers explains backtracking →

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.

Read how Optimization Algorithms: AI techniques for design, planning, and control problems explains backtracking →

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

Related concepts

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.