Backtracking — State Restoration Bugs That Break Solvers

Most real-world problems don't come with an obvious answer. Finding all valid ways to place chess queens on a board, generating every possible password combination, or solving a Sudoku puzzle — these all share one thing: there are many possible paths, and most of them are dead ends. Backtracking is the algorithmic strategy that lets you explore those paths efficiently without manually tracking which ones you've already failed at.

In this guide, we'll break down exactly what Backtracking is, why it was designed this way, and how to use it correctly in real projects by implementing production-grade search algorithms.

By the end you'll have both the conceptual understanding and practical code examples to use Backtracking with confidence.

What Backtracking Actually Does (and Why Brute Force Isn't Enough)

Brute force tries every possible combination regardless of whether it's already heading toward failure. Backtracking is smarter — it builds a solution incrementally, and the moment a partial solution violates a constraint, it stops pursuing that branch entirely. This is called 'pruning.'

Think of a decision tree. Every node is a choice. Brute force visits every single node. Backtracking visits a node, checks 'can this possibly lead to a valid answer?', and if the answer is no, it skips the entire subtree rooted there. That's the efficiency win.

The core loop is always the same: choose a candidate, place it, recurse deeper, then unchoose (undo the placement). That 'unchoose' step is what makes backtracking different from plain recursion — you're restoring state so the next candidate gets a clean slate to work with.

This pattern works beautifully for constraint satisfaction problems: puzzles, permutations, combinations, and graph coloring — anywhere the solution space is large but constraints filter most of it out early.

package io.thecodeforge.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

/**
 * io.thecodeforge implementation for generating power sets.
 */
public class SubsetGenerator {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3};
        List<List<Integer>> allSubsets = new ArrayList<>();

        generateSubsets(numbers, 0, new ArrayList<>(), allSubsets);

        System.out.println("All subsets of " + Arrays.toString(numbers) + ":");
        allSubsets.forEach(System.out::println);
        System.out.println("Total subsets: " + allSubsets.size());
    }

    private static void generateSubsets(
            int[] numbers,
            int startIndex,
            List<Integer> currentSubset,
            List<List<Integer>> results) {

        // Record a snapshot — O(N) copy
        results.add(new ArrayList<>(currentSubset));

        for (int i = startIndex; i < numbers.length; i++) {
            // CHOOSE
            currentSubset.add(numbers[i]);

            // EXPLORE
            generateSubsets(numbers, i + 1, currentSubset, results);

            // UNCHOOSE (Backtrack)
            currentSubset.remove(currentSubset.size() - 1);
        }
    }
}

Backtracking in C++: N-Queens Example

Backtracking is language-agnostic, but each language has its own idiomatic patterns for handling state. In C++, we typically use vectors and pass-by-reference to manage the board. The core logic remains identical: for each column, try each row, check safety, place queen, recurse, then backtrack (restore row to -1).

Here's the same N-Queens solver we showed in Java, now in C++. Notice how the feasibility check uses the same column-by-column approach, and the undo step is simply resetting the board cell to -1. C++ gives us fine-grained control over memory, but the backtracking pattern is unchanged.

This example also demonstrates the use of a recursive lambda (C++14 and later) or a separate function. We'll use a compact recursive function.

Compile with g++ -std=c++17 NQueens.cpp -o NQueens and run.

The output should match the Java version: 2 solutions for a 4×4 board.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void solveNQueens(int n, int col, vector<int>& queenInRow, vector<vector<int>>& solutions) {
    if (col == n) {
        solutions.push_back(queenInRow); // copy of current state
        return;
    }
    for (int row = 0; row < n; ++row) {
        if (isPlacementSafe(queenInRow, col, row)) {
            queenInRow[col] = row; // CHOOSE
            solveNQueens(n, col + 1, queenInRow, solutions); // EXPLORE
            // UNCHOOSE is implicit via row overwrite
        }
    }
}

bool isPlacementSafe(const vector<int>& queenInRow, int col, int row) {
    for (int prevCol = 0; prevCol < col; ++prevCol) {
        int prevRow = queenInRow[prevCol];
        if (prevRow == row || abs(prevRow - row) == abs(prevCol - col)) {
            return false; // PRUNE
        }
    }
    return true;
}

void printBoard(const vector<int>& queenInRow, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << (queenInRow[j] == i ? " Q " : " . ");
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    int n = 4;
    vector<int> queenInRow(n, -1);
    vector<vector<int>> solutions;
    solveNQueens(n, 0, queenInRow, solutions);
    cout << "Found " << solutions.size() << " solutions for " << n << "-Queens." << endl;
    for (auto& sol : solutions) {
        printBoard(sol, n);
    }
    return 0;
}

State Space Tree: Visualizing the Search Process

A state space tree is a visual representation of all possible states explored by backtracking. Each node represents a partial solution, and each branch represents a choice. The root is the empty state. Leaves are either complete solutions (recorded) or dead ends (pruned due to constraint violation).

For a 4-Queens board, the tree starts empty. At level 0 (column 0), we try rows 0-3. Placing a queen at row 0 leads to a subtree; placing at row 1 leads to another, etc. At level 1 (column 1), we try rows 0-3 again but prune those that conflict with the existing queens. The tree grows until we either reach a complete placement (solution) or find no valid rows, which becomes a dead end branch.

The diagram below shows a simplified state space tree for the first few levels of 4-Queens. The pruned branches are marked with an X. This visualization helps understand how backtracking explores only a fraction of the total possibilities.

For larger N, the tree becomes dense but pruned heavily. The key insight: the earlier a constraint is violated, the deeper the cut in the tree, saving enormous effort.

Pruning: The Feature That Makes Backtracking Fast

Generating all subsets is pure exploration — there are no invalid paths to prune. But backtracking really earns its keep when constraints let you eliminate huge branches early.

The N-Queens problem is the classic demonstration. Place N queens on an N×N chessboard so that no two queens attack each other (same row, column, or diagonal). A brute force approach would try all N^N placements. With pruning, the moment placing a queen creates a conflict, you stop and backtrack — you never explore any of the millions of board states that would follow from that illegal placement.

For an 8×8 board, brute force checks 16 million+ configurations. Backtracking with pruning checks roughly 15,000. That's the power of cutting entire subtrees.

The constraint check — the 'is this placement still valid?' question — is called the bounding function or feasibility check. Writing a tight, fast feasibility check is the single biggest lever you have for making backtracking solutions performant.

package io.thecodeforge.algorithm;

import java.util.ArrayList;
import java.util.List;

public class NQueensSolver {

    public static void main(String[] args) {
        int n = 4;
        List<int[]> solutions = new ArrayList<>();
        solveNQueens(n, 0, new int[n], solutions);

        System.out.println("Found " + solutions.size() + " solutions for " + n + "-Queens.");
        solutions.forEach(sol -> printBoard(sol, n));
    }

    private static void solveNQueens(int n, int col, int[] queenInRow, List<int[]> solutions) {
        if (col == n) {
            solutions.add(queenInRow.clone());
            return;
        }

        for (int row = 0; row < n; row++) {
            if (isPlacementSafe(queenInRow, col, row)) {
                queenInRow[col] = row; // CHOOSE
                solveNQueens(n, col + 1, queenInRow, solutions); // EXPLORE
                // UNCHOOSE is implicit via row overwrite
            }
        }
    }

    private static boolean isPlacementSafe(int[] queenInRow, int col, int row) {
        for (int prevCol = 0; prevCol < col; prevCol++) {
            int prevRow = queenInRow[prevCol];
            if (prevRow == row || Math.abs(prevRow - row) == Math.abs(prevCol - col)) {
                return false; // PRUNE branch
            }
        }
        return true;
    }

    private static void printBoard(int[] queenInRow, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(queenInRow[j] == i ? " Q " : " . ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

Recognizing When Backtracking Is the Right Tool

Backtracking isn't always the right choice. It's best when the problem has all three of these properties:

1. You need all solutions (or need to verify one exists), not just a single optimal one.
2. The solution is built incrementally — you make a series of choices.
3. Constraints can eliminate branches early — otherwise, you're just doing brute force.

Classic backtracking problems: N-Queens, Sudoku, generating permutations/combinations/subsets, word search on a grid, graph coloring, and the rat-in-a-maze problem.

Not a great fit for backtracking: finding the shortest path (use BFS/Dijkstra), problems with overlapping subproblems (use DP), or cases where you need statistical probability across all paths (use DP again).

package io.thecodeforge.algorithm;

import java.util.ArrayList;
import java.util.List;

public class PermutationGenerator {

    public static void main(String[] args) {
        String input = "ABC";
        List<String> results = new ArrayList<>();
        boolean[] used = new boolean[input.length()];
        
        backtrack(input.toCharArray(), used, new StringBuilder(), results);
        results.forEach(System.out::println);
    }

    private static void backtrack(char[] chars, boolean[] used, StringBuilder sb, List<String> results) {
        if (sb.length() == chars.length) {
            results.add(sb.toString());
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (used[i]) continue; // PRUNE

            used[i] = true; // CHOOSE
            sb.append(chars[i]);

            backtrack(chars, used, sb, results); // EXPLORE

            sb.deleteCharAt(sb.length() - 1); // UNCHOOSE
            used[i] = false;
        }
    }
}

When NOT to Use Backtracking

Backtracking is not a silver bullet. There are clear cases where it's the wrong tool, and knowing them will save you from wasted hours and poor performance.

1. Problems with no constraints to prune – If every branch is equally valid and you still need to explore all possibilities, backtracking is identical to brute force. Examples: generating all subsets of a set (no constraints), generating all permutations of a string with no duplicates. In these cases, the simple iterative or recursive approach is fine — backtracking adds complexity without benefit.

2. Problems where you only need one (or a few) solutions – Backtracking is designed to find all valid completions. If you just need to confirm existence or find the first solution, use a simpler search like DFS with early exit, or a greedy heuristic. For instance, solving a 9×9 Sudoku: backtracking finds one solution quickly, but if you want partial progress, constraint propagation alone may suffice.

3. Problems with overlapping subproblems – If the same partial state is reached via different paths, backtracking will recompute it each time. Dynamic programming (memoization) is exponentially faster. Classic example: Fibonacci numbers, where backtracking (literally trying all 2^n choices) is ridiculous; DP gives O(n).

4. Problems with a large branching factor and shallow depth – If you have many choices at each step but few steps to completion, the state space is wide but shallow. Backtracking still explores every branch, which can be enormous if the feasibility check doesn't prune heavily. Example: enumerating all possible assignments for a small scheduling problem with 30 options per slot and 5 slots: 30^5 = 24 million possibilities, and pruning may be weak.

5. Problems where the constraints are expensive to evaluate – If the feasibility check is O(n^2) or worse, and you're calling it at every node, the overhead can dwarf the benefit of pruning. In such cases, try to precompute or reduce the check's complexity.

Always profile before committing to backtracking — if a simpler solution exists, use it.

Backtracking vs Dynamic Programming vs Brute Force

Many engineers confuse backtracking with dynamic programming or brute force. They're cousins, but they handle constraints and overlapping work differently.

Brute force tries every combination with no pruning. It's simple but always exponential.

Backtracking prunes branches that can't lead to a valid solution. It's still worst-case exponential, but in practice it's much faster.

Dynamic programming caches results of overlapping subproblems to avoid recomputation. It works when the problem has optimal substructure and overlapping subproblems — things like Fibonacci, knapsack, edit distance.

The key difference: backtracking explores a tree and cuts dead branches. DP memoizes to avoid revisiting the same branch. When subproblems overlap heavily, DP wins. When the search space is large but most paths are quickly invalid, backtracking wins.

In some problems (like the Knight's Tour), both can be used — backtracking with a heuristic like Warnsdorff's rule is typically faster than DP because the state space of visited cells is hard to cache.

package io.thecodeforge.algorithm;

import java.util.*;

public class KnightTour {
    private static final int[] dx = {2, 1, -1, -2, -2, -1, 1, 2};
    private static final int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    
    public static boolean solveKnightTour(int n) {
        int[][] board = new int[n][n];
        // Fill with -1 to mark unvisited
        for (int[] row : board) Arrays.fill(row, -1);
        board[0][0] = 0;
        if (backtrack(board, 0, 0, 1, n)) {
            printBoard(board);
            return true;
        }
        System.out.println("No solution.");
        return false;
    }

    private static boolean backtrack(int[][] board, int x, int y, int step, int n) {
        if (step == n * n) return true; // all cells visited

        // Warnsdorff's heuristic: order moves by number of onward moves
        List<Move> moves = new ArrayList<>();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == -1) {
                int degree = countOnwardMoves(board, nx, ny, n);
                moves.add(new Move(nx, ny, degree));
            }
        }
        moves.sort(Comparator.comparingInt(m -> m.degree));

        for (Move m : moves) {
            board[m.x][m.y] = step;
            if (backtrack(board, m.x, m.y, step + 1, n)) return true;
            board[m.x][m.y] = -1; // undo
        }
        return false;
    }

    private static int countOnwardMoves(int[][] board, int x, int y, int n) {
        int count = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == -1)
                count++;
        }
        return count;
    }

    private static void printBoard(int[][] board) {
        for (int[] row : board) {
            for (int cell : row) System.out.printf("%2d ", cell);
            System.out.println();
        }
    }

    static class Move {
        int x, y, degree;
        Move(int x, int y, int degree) { this.x = x; this.y = y; this.degree = degree; }
    }
}

Backtracking vs Recursion: Understanding the Difference

Although backtracking is often implemented with recursion, they are not the same thing. Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. Backtracking is an algorithmic strategy that systematically explores candidate solutions and abandons those that cannot satisfy constraints.

You can have recursion without backtracking (e.g., a recursive factorial function) and backtracking without explicit recursion (e.g., using an explicit stack). The key distinction is the undo step: backtracking always includes state restoration after recursion, while plain recursion may just compute and return a value without side effects.

Another difference: backtracking always explores a decision tree with pruning; recursion can be used for problems that don't involve choices (e.g., tree traversal).

The table below summarizes the contrasts.

// Example: Recursive factorial (no backtracking)
public class Factorial {
    public static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
}

// Example: Backtracking subset generation (includes undo)
public class Subsets {
    void backtrack(int[] nums, int start, List<Integer> cur, List<List<Integer>> res) {
        res.add(new ArrayList<>(cur));
        for (int i = start; i < nums.length; i++) {
            cur.add(nums[i]);
            backtrack(nums, i + 1, cur, res);
            cur.remove(cur.size() - 1); // UNDO
        }
    }
}

Optimizing Backtracking: Heuristics, Ordering and Early Termination

Even with good pruning, backtracking can still be slow. Three optimisation techniques can drastically reduce runtime:

1. Variable Ordering (Most Constraining First) Choose the next variable with the most constraints (e.g., the cell with fewest remaining values in Sudoku). This minimises branching factor early.

2. Value Ordering (Least Constraining Value) Try values that are least likely to cause future conflicts. Warnsdorff's rule for Knight's Tour is a classic example — it reduces backtracks by up to 90%.

3. Forward Checking After making a choice, propagate constraints by eliminating values from future possibilities. If any future variable has no remaining valid values, prune immediately.

Forward checking is more code but often pays off for problems like Sudoku or graph coloring. Without it, you discover a dead end only after recursing deeper.

These techniques are common in constraint satisfaction problems (CSPs) and are the difference between a backtracking solver that finishes in seconds vs one that never completes.

package io.thecodeforge.algorithm;

public class SudokuSolver {
    private static final int SIZE = 9;
    private static final int BOX = 3;
    
    public boolean solve(int[][] board) {
        int[] empty = findEmpty(board);
        if (empty == null) return true; // solved
        int row = empty[0], col = empty[1];
        
        for (int num = 1; num <= SIZE; num++) {
            if (isValid(board, row, col, num)) {
                board[row][col] = num;
                if (solve(board)) return true;
                board[row][col] = 0; // undo
            }
        }
        return false;
    }

    private int[] findEmpty(int[][] board) {
        // Most constrained first: pick cell with fewest possibilities
        int minCount = SIZE + 1;
        int[] best = null;
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                if (board[r][c] == 0) {
                    int count = countValid(board, r, c);
                    if (count < minCount) {
                        minCount = count;
                        best = new int[]{r, c};
                    }
                }
            }
        }
        return best;
    }

    private int countValid(int[][] board, int row, int col) {
        int count = 0;
        for (int num = 1; num <= SIZE; num++) {
            if (isValid(board, row, col, num)) count++;
        }
        return count;
    }

    private boolean isValid(int[][] board, int row, int col, int num) {
        for (int c = 0; c < SIZE; c++) if (board[row][c] == num) return false;
        for (int r = 0; r < SIZE; r++) if (board[r][col] == num) return false;
        int boxRow = row - row % BOX;
        int boxCol = col - col % BOX;
        for (int r = boxRow; r < boxRow + BOX; r++)
            for (int c = boxCol; c < boxCol + BOX; c++)
                if (board[r][c] == num) return false;
        return true;
    }
}

Practice Problems: Solidify Your Backtracking Skills

The best way to master backtracking is to implement it across different problem types. Below are seven classic problems that cover the key patterns: subset generation, permutation, constraint satisfaction, and pathfinding. Each link leads to a detailed explanation with code on TheCodeForge.

1. Rat in a Maze – A classic pathfinding backtracking problem. Find all paths from top-left to bottom-right in a grid with obstacles. Demonstrates grid-state mutation and restoration.
2. [Solve Rat in a Maze →](https://thecodeforge.io/backtracking/rat-in-a-maze)
3. N-Queens Problem – Place N queens on an N×N board without conflicts. The quintessential backtracking problem. We covered it in depth above.
4. [Solve N-Queens →](https://thecodeforge.io/backtracking/n-queens)
5. Word Break Problem – Given a string and a dictionary, determine if the string can be segmented into dictionary words. Backtracking with pruning can solve it, though DP is more efficient for large inputs.
6. [Solve Word Break →](https://thecodeforge.io/backtracking/word-break)
7. Subsets (Power Set) – Generate all subsets of a given set. The simplest backtracking pattern – great for understanding the choose-explore-unchoose loop.
8. [Solve Subsets →](https://thecodeforge.io/backtracking/subsets)
9. Permutations – Generate all arrangements of a set of elements. Introduces the 'used' array pattern for avoiding repeats.
10. [Solve Permutations →](https://thecodeforge.io/backtracking/permutations)
11. Sudoku Solver – Fill a partially completed 9×9 grid so that every row, column, and 3×3 box contains digits 1-9. Demonstrates constraint propagation and forward checking.
12. [Solve Sudoku →](https://thecodeforge.io/backtracking/sudoku-solver)
13. M-Coloring Problem – Color a graph using at most M colors such that no two adjacent vertices share the same color. Classic constraint satisfaction problem.
14. [Solve M-Coloring →](https://thecodeforge.io/backtracking/m-coloring)

Start with Subsets and Permutations for the fundamentals, then move to N-Queens and Rat in a Maze for constraint-based problems. Finally, tackle Sudoku and M-Coloring for advanced pruning and ordering techniques.