↩️ Backtracking

Systematically search for solutions by building candidates incrementally and abandoning dead ends. Master N-Queens, Sudoku, and permutation generation.

Overview

ℹ️

What is Backtracking?

Backtracking incrementally builds candidates for solutions and abandons them (backtracks) when they can't lead to a valid solution. It's essentially DFS on the solution space tree. Key: prune branches that can't yield valid solutions to improve performance.

Key Backtracking Algorithms

N-Queens

Place N queens on N×N board so none attack each other

Time: O(N!)Space: O(N²)

Sudoku Solver

Solve 9×9 Sudoku puzzle using constraint satisfaction

Time: O(9^(n²))Space: O(n²)

Permutations

Generate all permutations of an array

Time: O(n!)Space: O(n)

Subsets

Generate all possible subsets of a set

Time: O(2ⁿ)Space: O(n)

Combination Sum

Find combinations summing to target (unlimited use)

Time: O(2^t)Space: O(t)

Interactive Visualizer

Backtracking Tree Visualization

↩️

N-Queens Backtracking Tree

See how the algorithm explores branches and backtracks when a constraint is violated.

Deep Dive: N-Queens

Time Complexity

Time: O(N!)

Space Complexity

Space: O(N²)

Paradigm

Systematic Search

💡

How It Works

Place queens row by row. For each row, try each column. If placement is safe, recurse to next row. If no safe column exists, backtrack to previous row and try next column.

python

def solveNQueens(n):
    cols, diag1, diag2 = set(), set(), set()
    result = []
    board = [["."]*n for _ in range(n)]
    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            board[row][col] = "Q"
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            backtrack(row + 1)
            board[row][col] = "."
            cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)
    backtrack(0)
    return result

1

Choose

Make a decision from available options at current state.

2

Constrain

Check if decision leads to a valid partial solution. If not, prune.

3

Recurse

Move to next decision point with updated state.

4

Unchoose

Undo the decision (backtrack) and try the next option.

Real-World Applications

Constraint Satisfaction

Sudoku, crosswords, map coloring, scheduling with constraints

Combinatorial Optimization

Traveling salesman, knapsack, graph coloring

AI & Game Playing

Chess engines, tic-tac-toe, puzzle solvers use backtracking

Configuration Problems

Assigning resources, timetabling, seating arrangements

Language Parsing

Context-free grammar parsing, regular expression matching

Path Finding

Finding all paths in a maze, Hamiltonian paths

Interview Questions

How is backtracking different from brute force?

Brute force generates all candidates then checks validity. Backtracking prunes invalid branches early, drastically reducing the search space. This is what makes N-Queens tractable for N up to 20+.

What is pruning in backtracking?

Pruning is eliminating branches that cannot lead to a valid solution without fully exploring them. Good pruning is the key to efficient backtracking. Example: in N-Queens, if two queens share same diagonal, prune.

How do you optimize backtracking?

1) Prune aggressively, 2) Order candidates wisely (most constrained first), 3) Use symmetry breaking, 4) Use bitmasks for faster constraint checks.

Can all backtracking problems be solved with DP?

No. Backtracking explores all possibilities (exhaustive). DP optimizes overlapping subproblems. If subproblems don't overlap, DP doesn't help. Backtracking is needed for combinatorial enumeration.

Knowledge Check

1. What is the central idea of backtracking?

2. What does 'pruning' mean in backtracking?

3. Time complexity of N-Queens?

4. When does backtracking stop exploring a branch?

5. What data structure is commonly used?

What's Next?

Explore Related Topics

Continue your learning journey: