Skip to main content

Classic Backtracking Problems

TL;DR​

Classic backtracking problems establish patterns applicable to any constraint satisfaction challenge. N-Queens: Place N queens on board with no attacks; constraint is safe placement checking; decision is column selection per row. Sudoku: Fill grid with digits 1-9 respecting row/column/box constraints; decision is digit selection per cell; constraint is uniqueness checking. Permutations: Generate ordered arrangements of n elements; decision is which element to pick next; no constraints (explore full tree). Combinations: Generate unordered selections of k from n elements; decision is include/exclude element; constraint is count tracking. Subsets: Generate all 2^n subsets; binary decision tree (include or exclude each element); no constraints. Sudoku shown here demonstrates complex multi-constraint satisfaction; optimize with digit frequency analysis and bit manipulation for large problems.

Core Concepts​

N-Queens Analysis​

Problem Statement: Place N queens on N×N board such no two queens attack (same row, column, or diagonal).

Key Insight: One queen per row means row is implicitly solved. Only need to track column and diagonal conflicts.

Constraint Checking: Two queens at (r1, c1) and (r2, c2) conflict if:

  • Same column: c1 == c2
  • Same diagonal: |r1 - r2| == |c1 - c2|

Optimization: Use sets or bitmasks to track occupied columns/diagonals. Check in O(1) instead of O(n).

Sudoku Solver Strategy​

Problem State: 9×9 grid with some cells filled; fill remaining cells with digits 1-9.

Constraints: Each digit appears once per row, column, and 3×3 box.

Optimization Strategies:

  • Find cell with minimum possible values (Most Constrained Variable heuristic)
  • Track possible digits per cell using sets or bitmasks
  • Eliminate candidates when digit placed in same row/column/box

Time Complexity: Best case O(n) with perfect heuristics; worst case O(9^n) where n = empty cells.

Permutations vs Combinations vs Subsets​

Permutations: Order matters. n! results for n elements. Decision: which element to pick next.

Combinations: Order doesn't matter. C(n,k) = n!/(k!(n-k)!) results. Decision: include/exclude element, but respect ordering to avoid duplicates.

Subsets: Include any number of elements. 2^n results. Binary tree structure.

Key Difference: Permutations pick all n elements every time; combinations pick k elements; subsets can have any size. Avoid duplicates by maintaining indices (next choice must be > previous choice).

Backtracking with Constraints​

Constraint Types:

  • Hard Constraints: Must be satisfied (N-Queens attacks, Sudoku digit uniqueness)
  • Soft Constraints: Preferred but not required (minimize steps, prefer certain values)

Checking Strategy: Always check before recursing. If constraint fails, don't recurse.

Pruning Benefit: One invalid partial solution eliminates entire subtree. In Sudoku, placing invalid digit immediately fails; pruning can eliminate millions of branches.

Key Algorithms​

Sudoku Solver Pseudo-code​

function solveSudoku(grid):
    for each cell in grid:
        if cell is empty:
            for each digit 1-9:
                if digit is valid in cell (not in row/col/box):
                    place digit
                    if solveSudoku(grid):
                        return true
                    remove digit (backtrack)
            return false (no valid digit found)
    return true (all cells filled)

Permutations with Optimization​

Swap-based approach: Swap elements in-place, swap back on backtrack. Avoids copying arrays.

Combination Constraint​

To avoid duplicates, track starting index. Next choice must be >= current index to maintain order.

Practical Example​

# Sudoku Solver
def solve_sudoku(board):
    """
    Solve Sudoku puzzle in-place.
    board: 9x9 list of lists, 0 represents empty cell
    """
    def is_valid(row, col, digit):
        """Check if digit can be placed at (row, col)"""
        # Check row
        if digit in board[row]:
            return False

        # Check column
        if digit in [board[i][col] for i in range(9)]:
            return False

        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == digit:
                    return False

        return True

    def backtrack():
        """Try to fill empty cells"""
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:
                    # Try digits 1-9
                    for digit in range(1, 10):
                        if is_valid(row, col, digit):
                            board[row][col] = digit

                            if backtrack():
                                return True

                            # Backtrack
                            board[row][col] = 0

                    return False  # No valid digit found

        return True  # All cells filled

    backtrack()
    return board

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

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if nums[i] not in path:
                path.append(nums[i])
                backtrack(path)
                path.pop()

    backtrack([])
    return result

# Combinations
def combine(n, k):
    """Generate all combinations of k elements from 1..n"""
    result = []

    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return

        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()

    backtrack(1, [])
    return result

# Tests
sudoku_board = [
    [5,3,0,0,7,0,0,0,0],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,0,0,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [0,0,0,0,8,0,0,7,9]
]

solve_sudoku(sudoku_board)
print("Sudoku solved:")
for row in sudoku_board:
    print(row)

print("\nPermutations of [1,2,3]:")
perms = permute([1, 2, 3])
print(f"Count: {len(perms)}")

print("\nCombinations C(4,2):")
combs = combine(4, 2)
print(combs)

Common Pitfalls​

warning

Sudoku digit elimination errors: When placing digit, forgetting to update possible values for remaining cells. Leads to inefficient search or missed optimizations.

Permutations with duplicates: Not using visited array or similar mechanism. Same element picked multiple times or duplicates in result.

Combinations allowing duplicates: Forgetting to maintain ordering constraint (next choice > previous choice). Generates [1,2] and [2,1] as different combinations.

Inefficient Sudoku checking: Scanning entire row/column/box each time. Pre-compute sets or use bit manipulation for O(1) validation.

Not finding optimal heuristic: Sudoku solver picks cells in arbitrary order. Picking cell with fewest possibilities (Most Constrained Variable) can reduce search space exponentially.

Returning early vs collecting all solutions: For Sudoku, return as soon as found. For permutations/combinations, continue exploring to collect all. Make sure logic matches intent.

Self-Check​

  1. In Sudoku, why is checking constraints before recursing important? What happens if you only check after completion?
  2. Why do permutations require a visited array but combinations only require a starting index?
  3. How would you modify the Sudoku solver to find the first solution in minimum time?

One Takeaway​

info

Classic problems demonstrate backtracking patterns: constraint satisfaction (Sudoku), exhaustive generation (permutations/combinations), and pruning effectiveness (N-Queens). The breakthrough is recognizing problem structure: Is it CSP (Sudoku), exhaustive generation (perms), or counting (combinations)? Choose algorithms accordingly. For each pattern, implement constraint checking rigorously and pruning intelligently—this transforms exponential search into practical solutions.

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.