# Backtracking

> Systematic trial-and-error search technique that builds solutions incrementally, abandoning candidates as soon as they cannot lead to a valid solution

- Skill: `lev-os/backtracking` (Agent Skill)
- Install (CLI): `npx skillmds@latest add lev-os/backtracking`
- Raw SKILL.md: https://api.skillmd.com/api/skills/lev-os/backtracking/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: lev-os (https://skillmd.com/u/lev-os)
- Updated: 2026-09-10
- Page: https://skillmd.com/skills/lev-os/backtracking

---


# Backtracking Algorithm Paradigm

## What It Is
A systematic trial-and-error search technique that builds solutions incrementally, abandoning (backtracking from) candidates as soon as it determines they cannot lead to a valid solution. Think of it as exploring a decision tree depth-first, pruning branches that violate constraints. The key insight: undo bad choices and try alternatives rather than exploring every possibility blindly.

## When to Use It
- Need to find **all valid solutions** (not just one optimal solution)
- Problem involves **constraint satisfaction** (e.g., placing queens, solving Sudoku)
- Solution is a **sequence of choices** with validity constraints
- Choices have dependencies (can't be made independently like greedy)
- Exhaustive search is required but can be pruned intelligently
- Problem space is tree-like (make choice, recurse, undo choice)

**Key Signal**: If you're thinking "try this, if it doesn't work, undo it and try that" → backtracking.

## Execution Steps

### 1. Choose (Make a Decision)
Select one option from available choices at current decision point. This extends the partial solution by one step. Start with first option if exploring all solutions.

**Action**: Pick a candidate (e.g., place queen in column i, assign digit d to cell, include element in subset). Add this choice to current partial solution.

### 2. Check Validity
Verify if the current partial solution satisfies all constraints. This is the pruning step - reject invalid paths early before exploring deeper.

**Action**: Run constraint checks (e.g., no two queens attack each other, Sudoku row/column/box rules, subset sum not exceeded). If invalid, skip to step 4 (backtrack).

### 3. Explore (Recurse)
If valid, move forward with this choice and recursively solve the remaining subproblem. If this is a complete solution, record it and potentially return (depending on whether you need one or all solutions).

**Action**: Recursively call backtracking function with updated state. If complete solution found and only need one, return success. If need all solutions, store it and continue.

### 4. Backtrack (Undo)
Remove the last choice from the partial solution (undo the decision). Try the next alternative at this decision level.

**Action**: Restore state to before step 1 (e.g., remove queen, clear cell, exclude element). Move to next candidate. If no more candidates, return to previous decision level.

### 5. Repeat
Continue until all possibilities at current level are exhausted, then backtrack to previous level. Process completes when all branches explored or solution found (if only need one).

**Action**: Loop through all candidates at each decision point. Recursion handles moving between levels. Base case: solution complete (return it) or no valid choices (return failure).

## Real-World Applications

**Constraint Satisfaction Problems**
- Sudoku solver: fill grid satisfying row/column/box constraints
- N-Queens: place N queens on N×N board with no attacks
- Graph coloring: assign colors to nodes so no adjacent nodes share color
- Crossword puzzle generation: place words satisfying constraints

**Combinatorial Search**
- Permutation generation: find all orderings of elements
- Subset sum: find all subsets summing to target
- Combination generation: select k items from n (C(n,k))
- Partition problem: split set into two equal-sum subsets

**Game Solving**
- Maze solving: find path from start to goal
- Tic-tac-toe/chess move generation: explore game tree
- Puzzle solving (8-puzzle, Rubik's cube): search state space

**Path Finding**
- Hamiltonian path: visit each vertex exactly once
- Traveling salesman (small instances): find optimal tour
- Knight's tour: chess knight visits each square once

**Resource Allocation**
- Job assignment: assign workers to tasks with constraints
- Exam scheduling: schedule exams avoiding conflicts
- Timetable generation: assign classes to rooms/times

**Natural Language Processing**
- Syntax tree parsing: find valid parse trees for sentences
- Word break problem: segment sentence into valid words
- Regular expression matching (with backtracking)

## Anti-Patterns

**Not pruning invalid paths early** → Explores exponentially many invalid branches; check constraints ASAP after each choice.

**Using backtracking for optimization without pruning** → Extremely slow; add bounds/heuristics or use branch-and-bound instead.

**Forgetting to restore state** → Leads to incorrect solutions; always undo changes when backtracking.

**Exploring same state multiple times** → Wastes time; consider memoization or marking visited states.

**Using when greedy/DP suffices** → Backtracking is exponential; if problem has greedy property or overlapping subproblems, use faster methods.

**Poor choice ordering** → Exploring likely-to-fail branches first; use heuristics (e.g., most constrained variable first).

## Success Metrics
- Correctness: finds all valid solutions (for enumeration) or any valid solution (for search)
- Pruning effectiveness: ratio of explored nodes to total nodes (lower is better)
- Time performance: acceptable runtime on target problem sizes
- Space efficiency: recursion depth manageable (< 1000 levels typically)
- Code clarity: recursive structure clearly matches problem structure

## Related Frameworks
- **Depth-First Search (DFS)**: Backtracking is DFS with constraint checking and pruning
- **Branch and Bound**: Backtracking + bounding functions for optimization
- **Dynamic Programming**: When subproblems overlap, replace backtracking with DP
- **Constraint Programming**: Declarative approach with propagation and backtracking
- **A* Search**: Informed search with heuristics for optimal paths

## Common Pitfalls
- Not implementing proper base case (infinite recursion)
- Modifying global state without restoration (bugs in multi-branch exploration)
- Confusing "find one solution" vs. "find all solutions" (early return logic)
- Deep recursion causing stack overflow (convert to iterative with explicit stack)
- Not handling empty input or boundary cases (0 elements, 1 element)
- Inefficient constraint checking (recompute entire state instead of incremental)

## Tools & Resources
- **Visualization**: Algorithm Visualizer (algorithm-visualizer.org), Recursion Tree Visualizer
- **Practice Platforms**: LeetCode backtracking tag (~100 problems), HackerRank recursion section
- **Books**: "Algorithms" (Sedgewick & Wayne), "Programming Pearls" (Bentley)
- **Debugging**: Add trace prints showing decision depth and choices, visualize recursion tree
- **Profiling**: Count number of recursive calls, measure pruning effectiveness

## Classic Backtracking Problems

**N-Queens**: Place N queens on N×N board, no two queens attack each other.
- State: queen positions by row
- Constraint: no two queens share row/column/diagonal
- Time: O(N!) without pruning, much better with constraint checking

**Sudoku**: Fill 9×9 grid with digits 1-9 satisfying row/column/box constraints.
- State: partially filled grid
- Constraint: each digit appears once per row/column/3×3 box
- Time: Exponential in unfilled cells, but heavy pruning makes it practical

**Subset Sum**: Find all subsets of array summing to target T.
- State: current subset and remaining elements
- Constraint: current sum ≤ target
- Time: O(2^n) worst case, pruning helps significantly

**Permutations**: Generate all orderings of n elements.
- State: current permutation prefix
- Constraint: each element used once
- Time: O(n!) - must explore all leaves

**Graph Coloring**: Assign colors to vertices so no adjacent vertices share color.
- State: color assignments for vertices
- Constraint: adjacent vertices have different colors
- Time: O(m^n) where m = colors, n = vertices

## Optimization Techniques

**Choice Ordering (Heuristics)**: Try most promising branches first (fail-fast or succeed-fast).

**Constraint Propagation**: When making a choice, deduce implications and prune early.

**Memoization**: Cache results for states that recur (hybrid backtracking-DP).

**Iterative Deepening**: Limit recursion depth, gradually increase (avoid stack overflow).

**Symmetry Breaking**: Avoid exploring equivalent states (e.g., in N-Queens, only check half of first row).

**Forward Checking**: Before making choice, verify remaining choices still have valid options.

---
*Framework Type*: Algorithm Design Paradigm
*Domain*: Computer Science, Constraint Satisfaction
*Practitioner Score*: 8/10 - Essential for constraint problems, widely used in game AI, solvers
*Complexity*: Medium - Recursive thinking required, state management can be tricky
*Prerequisites*: Recursion, depth-first search, constraint satisfaction concepts