Common Backtracking Patterns

Imagine you're looking at a crossword puzzle, but instead of reading clues, you need to verify whether a given word exists somewhere in the grid. The word might wind its way through the grid in any direction—horizontally, vertically, or diagonally—turning at each cell to find its path. This is the Word Search problem, a quintessential backtracking challenge that appears across software engineering domains from game development to text processing to bioinformatics.

The Word Search problem is deceptively simple to state but profoundly instructive in its solution. It exemplifies how backtracking transforms what could be an intractable brute-force exploration into a structured, efficient search through a solution space. By mastering this problem, you gain intuition that transfers directly to countless grid-based exploration challenges.

Let us establish the problem with mathematical precision before exploring solutions.

The Word Search Problem:

Given:

• An m × n grid of characters board[m][n]
• A string word of length k

Determine whether word exists in the grid, where the word can be constructed from letters of sequentially adjacent cells, and the same cell may not be used more than once.

Adjacency Definition:

Two cells are "adjacent" if they share an edge. This means each cell (except those on the boundary) has exactly 4 neighbors: up, down, left, and right. Importantly, diagonal cells are not adjacent in the standard formulation.

Constraints:

• 1 ≤ m, n ≤ 6 (for the LeetCode variant)
• 1 ≤ word.length ≤ 15
• board and word consist of only lowercase and uppercase English letters

The constraint sizes hint at the exponential nature of the problem—the solution space is too large for polynomial algorithms but small enough that pruned backtracking works efficiently.

Before implementing a solution, let's understand why backtracking is the right paradigm for this problem.

The Solution Space Structure:

Imagine trying to find the word "HELLO" in a grid. Your solution space looks like a tree:

• Root: Each cell that contains 'H' is a potential starting point
• Level 1: From each 'H', each adjacent cell containing 'E' is a potential second step
• Level 2: From each 'E', each adjacent (unvisited) cell containing 'L' is a potential third step
• And so on...

This forms a search tree where each path from root to leaf represents a sequence of choices. We're looking for a path of length k (the word length) where each node's character matches the corresponding character in the word.

Why Not Brute Force?

Theoretically, we could:

1. Generate all possible paths of length k starting from any cell
2. Filter paths where the characters spell our word

But the number of such paths is astronomical. From each cell, we have up to 4 choices. For a path of length k, that's potentially O(4^k) paths from each of m × n cells. For a 6×6 grid and a 15-character word, that's 36 × 4^15 ≈ 38 billion potential paths—clearly infeasible.

Recall the universal backtracking template from earlier in this chapter:

function backtrack(state):
    if isComplete(state):
        processResult()
        return
    
    for choice in getChoices(state):
        if isValid(choice, state):
            make(choice)           // Choose
            backtrack(newState)    // Explore
            undo(choice)           // Unchoose

Let's map this template to the Word Search problem:

State: Our current position (row, col) in the grid and the current index i in the word we're trying to match.

isComplete: We've matched all characters, i.e., i == word.length.

getChoices: The four adjacent cells: (row-1, col), (row+1, col), (row, col-1), (row, col+1).

isValid: The cell is within bounds, hasn't been visited in the current path, and its character matches word[i].

make(choice): Mark the cell as visited.

undo(choice): Unmark the cell as visited (the critical backtracking step).

Let's dissect each component of our solution to understand the nuances that make it work correctly and efficiently.

The Visited-Cell Strategy:

Notice that we don't use a separate visited set or matrix. Instead, we temporarily modify the board itself by replacing the current cell's character with a sentinel value ('#'). This is a common optimization:

1. Constant-time marking: board[row][col] = '#' is O(1)
2. Space efficiency: No additional O(m×n) visited matrix needed
3. Automatic propagation: The modification is visible to all recursive calls
4. Easy restoration: We save the original character and restore it during backtracking

This technique is safe because we never look at the value of a '#' cell—we only check if the character matches the word, which '#' never will (assuming the word contains only letters).

The Order of Checks:

Our validity check combines multiple conditions:

if (row < 0 or row >= rows or 
    col < 0 or col >= cols or 
    board[row][col] != word[index]):
    return False

The order matters for short-circuit evaluation:

1. Bounds check first: Accessing board[row][col] with invalid indices would crash
2. Character match last: Only checked if we're in bounds

The character match implicitly handles the visited check—a visited cell contains '#', which won't match any letter in the word.

The Direction Array Pattern:

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up

This is a classic pattern for grid traversal. Each tuple represents (row_delta, col_delta). Using an array instead of four separate recursive calls:

• Makes the code cleaner and more maintainable
• Makes it trivial to add diagonal movement (just add 4 more tuples)
• Enables easy direction ordering for problems where it matters

Understanding the complexity of backtracking algorithms is crucial but often tricky. Let's analyze our Word Search solution carefully.

Time Complexity: O(m × n × 4^L)

Where:

• m = number of rows
• n = number of columns
• L = length of the word

Derivation:

1. Starting points: We potentially start from each of the m × n cells
2. Branching factor: From each cell, we explore up to 4 directions
3. Depth: We recurse up to L levels (the word length)
4. Work per call: O(1) for bounds check and character comparison

At first glance, this suggests O(m × n × 4^L). But wait—we said 4 directions, yet after the first step, we can't go back to where we came from (it's marked visited). So the actual branching factor is closer to 3 after the first step.

However, we traditionally express this as O(4^L) because:

• The first step truly has 4 options
• Using 3 instead gives O(4 × 3^(L-1)), which is still O(4^L) asymptotically
• The constant factor difference doesn't affect big-O

Space Complexity: O(L)

The space complexity is determined by:

1. Recursion stack: Maximum depth is L (the word length)
2. Board modification: We modify the board in-place, using O(1) extra space

If we used a separate visited matrix, space would be O(m × n), but our in-place marking avoids this.

While our basic solution is correct and reasonably efficient, several optimizations can dramatically improve performance for challenging inputs.

Optimization 1: Character Frequency Check (Pre-pruning)

Before starting the search, verify that the grid contains at least as many of each character as the word requires:

from collections import Counter

def exist_optimized(board, word):
    # Count characters in board
    board_count = Counter(char for row in board for char in row)
    word_count = Counter(word)
    
    # Early termination if word can't possibly exist
    for char, count in word_count.items():
        if board_count[char] < count:
            return False
    
    # ... proceed with backtracking

This O(m × n + L) preprocessing step can immediately return False for impossible cases.

Optimization 2: Reverse Word Search

If the last character of the word is rarer in the grid than the first character, search for the reversed word instead:

if board_count[word[0]] > board_count[word[-1]]:
    word = word[::-1]  # Search backwards

This doesn't change the worst case but significantly improves average case by reducing the number of starting points.

The Word Search problem has many variations that test different aspects of backtracking mastery. Understanding these prepares you for interview variations and real-world applications.

Variation 1: Word Search II (Find All Words)

Given a list of words instead of a single word, find all words that exist in the grid. The naive approach would run Word Search for each word, but a Trie-based approach is much more efficient:

• Build a Trie from all target words
• Run backtracking once, checking the Trie at each step
• Remove found words from the Trie to avoid duplicates

This reduces time from O(W × m × n × 4^L) to O(m × n × 4^L') where W is the number of words and L' is the maximum word length.

Variation 2: Counting All Occurrences

Instead of just determining if a word exists, count how many distinct paths spell the word:

def count_occurrences(board, word):
    count = 0
    
    def backtrack(row, col, index):
        nonlocal count
        if index == len(word):
            count += 1
            return  # Don't return True—continue searching
        
        # ... same logic but don't return early on success
    
    # ... search from all cells
    return count

The key difference: we don't return immediately when we find a match; we increment a counter and continue to find all matches.

The Word Search problem is a foundational example of how backtracking elegantly solves grid exploration problems. Let's consolidate the key insights:

What's next:

With grid-based backtracking mastered, we'll explore the Combination Sum family of problems—a different flavor of backtracking where we build numeric combinations that sum to a target. These problems introduce new concerns like handling duplicates and optimizing the choice generation process.