Backtracking Fundamentals

TL;DR

Backtracking systematically explores the state space by building solutions incrementally and abandoning paths that violate constraints. State Space Tree: Each node represents a partial solution; edges represent decisions; leaves represent complete solutions. Decision Tree: At each step, try each valid choice, recurse, then undo (backtrack) to try next choice. Pruning: Eliminate branches early by checking constraints; failed constraint means entire subtree is invalid. Core Template: function backtrack(path, state, constraints) - if valid complete solution return; for each valid choice: add to path, recurse, remove from path. N-Queens Example: Place queens row by row; for each row try each column, check if placement is safe (no conflicts with already-placed queens), recurse or backtrack. Backtracking combines exhaustive search with intelligent pruning to efficiently solve constraint satisfaction problems.

Core Concepts

State Space and Exploration

The state space is the universe of all possible solutions. Backtracking explores this space systematically using a tree structure:

State Space Tree: Each node represents a partial solution state. Root is empty state; edges represent decisions (choices). Internal nodes have children for each valid next choice; leaf nodes represent complete solutions.

Depth: Depth = number of decisions made. Problem structure determines maximum depth (e.g., N-Queens has depth N).

Branching Factor: Number of choices at each node. Reduces as we make more decisions due to constraint propagation.

Decision Making and Choice

At each step, backtracking makes a choice from remaining valid options:

Choice Point: Location in recursion where we try multiple alternatives. Try one choice, recurse fully, then undo (backtrack) and try next.

Try-Recurse-Undo Pattern: Core backtracking loop. Add choice to current solution → recurse with new state → remove choice to restore state.

Validity Check: Before recursing, verify choice doesn't violate constraints. This pruning prevents exploring invalid subtrees.

Pruning and Constraint Checking

Pruning is the key to backtracking efficiency. It eliminates entire branches containing no valid solutions:

Early Termination: When partial solution violates constraint, no complete solution extending it can be valid. Prune entire subtree.

Incremental Constraint Checking: Check constraints as we build solution, not after completion. Catches failures early.

Bounding: If current path's metric (e.g., distance, cost) exceeds known best solution, prune. Especially useful in optimization.

Constraint Satisfaction Problem (CSP)

Backtracking excels at CSPs: find assignment to variables satisfying all constraints.

Variables: Entities to assign values (e.g., rows, columns in N-Queens)

Domain: Possible values for each variable (e.g., columns 1-N)

Constraints: Restrictions on variable assignments (e.g., no two queens attack)

Solution: Assignment where all constraints satisfied. Backtracking finds one or all solutions.

Key Algorithms

General Backtracking Template

function backtrack(path, state, constraints):
    if path is complete solution:
        return success

    for each valid choice in remaining choices:
        if choice doesn't violate constraints:
            add choice to path
            update state

            if backtrack(path, state, constraints):
                return success

            remove choice from path
            undo state update

    return failure (no valid solution found)

N-Queens Problem Template

Problem: Place N queens on N×N chessboard such no two attack.

State Space: Queen positions; tree has depth N (one queen per row).

Constraints: No two queens in same column or diagonal.

Pruning: After placing queen in row i, check if it attacks any previously placed queens. If so, prune.

Subset Generation

Problem: Generate all subsets of given set.

State Space: Include/exclude each element; tree has depth n (one decision per element).

Pruning: No constraints; explore entire tree but structure is optimal.

Practical Example

Python

# N-Queens Problem
def solve_n_queens(n):
    """
    Find all valid placements of N queens on N×N board.
    Returns list of solutions, each is list of column positions.
    """
    result = []
    board = [-1] * n  # board[i] = column of queen in row i

    def is_safe(row, col):
        """Check if placing queen at (row, col) is safe"""
        for prev_row in range(row):
            prev_col = board[prev_row]

            # Check column conflict
            if prev_col == col:
                return False

            # Check diagonal conflict
            if abs(prev_row - row) == abs(prev_col - col):
                return False

        return True

    def backtrack(row):
        """Try to place queen in given row"""
        if row == n:
            # Found valid solution
            result.append(board[:])
            return

        for col in range(n):
            if is_safe(row, col):
                # Place queen and recurse
                board[row] = col
                backtrack(row + 1)
                # Backtrack (implicit - just move to next col)

    backtrack(0)
    return result

# Subset Generation
def generate_subsets(nums):
    """Generate all subsets (power set) of given list"""
    result = []

    def backtrack(start, current_subset):
        # Add current subset to result
        result.append(current_subset[:])

        for i in range(start, len(nums)):
            # Include nums[i]
            current_subset.append(nums[i])
            backtrack(i + 1, current_subset)
            # Exclude nums[i] (backtrack)
            current_subset.pop()

    backtrack(0, [])
    return result

# Permutations
def generate_permutations(nums):
    """Generate all permutations of given list"""
    result = []

    def backtrack(remaining, current_perm):
        if not remaining:
            result.append(current_perm[:])
            return

        for i in range(len(remaining)):
            # Choose element at index i
            elem = remaining[i]
            current_perm.append(elem)

            # Recurse with remaining elements (excluding chosen one)
            new_remaining = remaining[:i] + remaining[i+1:]
            backtrack(new_remaining, current_perm)

            # Backtrack
            current_perm.pop()

    backtrack(nums, [])
    return result

# Tests
print("N-Queens (N=4):")
solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions")
for sol in solutions:
    print(sol)

print("\nSubsets of [1, 2, 3]:")
subsets = generate_subsets([1, 2, 3])
print(f"Total subsets: {len(subsets)}")
for s in subsets:
    print(s)

print("\nPermutations of [1, 2, 3]:")
perms = generate_permutations([1, 2, 3])
print(f"Total permutations: {len(perms)}")
for p in perms:
    print(p)

Java

import java.util.*;

public class BacktrackingFundamentals {

    // N-Queens Problem
    public static List<List<Integer>> solveNQueens(int n) {
        List<List<Integer>> result = new ArrayList<>();
        int[] board = new int[n]; // board[i] = column of queen in row i
        Arrays.fill(board, -1);

        backtrackQueens(board, 0, result);
        return result;
    }

    private static boolean isSafe(int[] board, int row, int col) {
        for (int prevRow = 0; prevRow < row; prevRow++) {
            int prevCol = board[prevRow];

            // Check column conflict
            if (prevCol == col) return false;

            // Check diagonal conflict
            if (Math.abs(prevRow - row) == Math.abs(prevCol - col)) {
                return false;
            }
        }
        return true;
    }

    private static void backtrackQueens(int[] board, int row,
                                       List<List<Integer>> result) {
        if (row == board.length) {
            List<Integer> solution = new ArrayList<>();
            for (int col : board) {
                solution.add(col);
            }
            result.add(solution);
            return;
        }

        for (int col = 0; col < board.length; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                backtrackQueens(board, row + 1, result);
            }
        }
    }

    // Subset Generation
    public static List<List<Integer>> generateSubsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrackSubsets(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrackSubsets(int[] nums, int start,
                                        List<Integer> current,
                                        List<List<Integer>> result) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrackSubsets(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }

    // Permutations
    public static List<List<Integer>> generatePermutations(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> remaining = new ArrayList<>();
        for (int num : nums) {
            remaining.add(num);
        }
        backtrackPermutations(remaining, new ArrayList<>(), result);
        return result;
    }

    private static void backtrackPermutations(List<Integer> remaining,
                                             List<Integer> current,
                                             List<List<Integer>> result) {
        if (remaining.isEmpty()) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < remaining.size(); i++) {
            int elem = remaining.get(i);
            current.add(elem);

            List<Integer> newRemaining = new ArrayList<>(remaining);
            newRemaining.remove(i);

            backtrackPermutations(newRemaining, current, result);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println("N-Queens (N=4):");
        List<List<Integer>> solutions = solveNQueens(4);
        System.out.println("Found " + solutions.size() + " solutions");
        for (List<Integer> sol : solutions) {
            System.out.println(sol);
        }

        System.out.println("\nSubsets of [1, 2, 3]:");
        List<List<Integer>> subsets = generateSubsets(new int[]{1, 2, 3});
        System.out.println("Total subsets: " + subsets.size());

        System.out.println("\nPermutations of [1, 2, 3]:");
        List<List<Integer>> perms = generatePermutations(new int[]{1, 2, 3});
        System.out.println("Total permutations: " + perms.size());
    }
}

TypeScript

// N-Queens Problem
function solveNQueens(n: number): number[][] {
    const result: number[][] = [];
    const board = Array(n).fill(-1);

    function isSafe(row: number, col: number): boolean {
        for (let prevRow = 0; prevRow < row; prevRow++) {
            const prevCol = board[prevRow];

            // Check column conflict
            if (prevCol === col) return false;

            // Check diagonal conflict
            if (Math.abs(prevRow - row) === Math.abs(prevCol - col)) {
                return false;
            }
        }
        return true;
    }

    function backtrack(row: number): void {
        if (row === n) {
            result.push([...board]);
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row] = col;
                backtrack(row + 1);
            }
        }
    }

    backtrack(0);
    return result;
}

// Subset Generation
function generateSubsets<T>(nums: T[]): T[][] {
    const result: T[][] = [];

    function backtrack(start: number, current: T[]): void {
        result.push([...current]);

        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    }

    backtrack(0, []);
    return result;
}

// Permutations
function generatePermutations<T>(nums: T[]): T[][] {
    const result: T[][] = [];

    function backtrack(remaining: T[], current: T[]): void {
        if (remaining.length === 0) {
            result.push([...current]);
            return;
        }

        for (let i = 0; i < remaining.length; i++) {
            const elem = remaining[i];
            current.push(elem);

            const newRemaining = remaining.slice(0, i).concat(remaining.slice(i + 1));
            backtrack(newRemaining, current);

            current.pop();
        }
    }

    backtrack(nums, []);
    return result;
}

// Tests
console.log("N-Queens (N=4):");
const solutions = solveNQueens(4);
console.log(`Found ${solutions.length} solutions`);

console.log("\nSubsets of [1, 2, 3]:");
const subsets = generateSubsets([1, 2, 3]);
console.log(`Total subsets: ${subsets.length}`);

console.log("\nPermutations of [1, 2, 3]:");
const perms = generatePermutations([1, 2, 3]);
console.log(`Total permutations: ${perms.length}`);

Common Pitfalls

warning

Forgetting to backtrack: Modify state but don't restore it before trying next choice. State gets corrupted; later iterations see wrong state.

Weak constraint checking: Only check constraints at solution completion, not during building. Misses early pruning opportunities; explores invalid subtrees.

Infinite recursion: Base case missing or unreachable. Add clear termination condition (complete solution or no valid choices).

Including invalid choices: Don't filter invalid choices before recursing. Recurse on invalid state; deeper recursion still invalid. Filter first.

Pruning too aggressively: Over-prune valid branches due to incorrect constraint logic. Causes missed solutions. Verify constraint conditions carefully.

Performance without metrics: Backtracking can be exponential. Without pruning or early termination, explores huge search space. Always profile; add metrics if needed.

Self-Check

1. In N-Queens, why do we only check previously-placed queens when validating a placement? Why not future queens?
2. How many subsets does a set with n elements have? Why is this the optimal tree structure for subsets?
3. Modify the N-Queens solution to count all solutions without storing them. What's the minimum state you need?

One Takeaway

info

Backtracking is systematic state space exploration with intelligent pruning. The core insight is the try-recurse-undo pattern: make a choice, fully explore consequences, restore state, try next choice. Success depends on two factors: thorough constraint checking to prune invalid branches early, and correct base case to recognize complete solutions. Master these elements, and you can solve any constraint satisfaction problem.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson Education.