Grid Backtracking

To solve a maze, you must be willing to walk down a path, realize it's a dead end, and have the wisdom to turn back.

You've seen how backtracking can explore all permutations or combinations. Now, we'll apply that same "try, fail, and undo" logic to navigate the implicit graph of a grid, searching for a path that satisfies a specific set of constraints.

Problem: Word Search (LeetCode Link): Given an m x n grid of characters and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, but the same letter cell may not be used more than once in the word. 💡 Hint 💡 Hint

Adapting Backtracking to a Grid

Backtracking is a methodical way of trying out different sequences of decisions until you find one that "works." For grid problems, this means exploring implicit paths through the grid, where each cell can be thought of as a node in a graph.

The main challenge is managing the state—the "path" you're currently on—to avoid reusing cells.

The "Mark and Unmark" Technique

The most common way to manage the path is to modify the grid in-place.

Mark (Choose): When you move to a cell (r, c), change its value to a special character (like '#') to signify, "This cell is currently in my path."
Explore: Make your recursive calls to the neighbors.
Unmark (Unchoose): After the recursive calls return, you must restore the cell's original character. board[r][c] = original_char. This "un-marks" the cell, effectively removing it from the current path and making it available for other branches of the recursion.

Walkthrough: Solving "Word Search"

Let's apply the "Choose, Explore, Unchoose" pattern.

Main Loop: Iterate through each cell (r, c). If board[r][c] matches the first letter of the word, launch a backtracking search from there.
Backtracking Function backtrack(r, c, index):
- Success Case: If index reaches the end of the word, we've found a valid path. Return true.
- Failure Cases: Return false if the cell is out of bounds or its character doesn't match word[index].
- Choose & Mark: temp = board[r][c], then board[r][c] = '#'.
- Explore: Recursively call backtrack for all four neighbors with index + 1. If any call returns true, we've found a solution, so return true immediately.
- Unchoose & Unmark: If no neighbor found a solution, restore the cell: board[r][c] = temp. Return false.

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    
    def backtrack(r, c, index):
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
            return False
        
        # Choose & Mark
        temp = board[r][c]
        board[r][c] = '#'
        
        # Explore neighbors
        found = (backtrack(r + 1, c, index + 1) or
                 backtrack(r - 1, c, index + 1) or
                 backtrack(r, c + 1, index + 1) or
                 backtrack(r, c - 1, index + 1))
        
        # Unchoose & Unmark
        board[r][c] = temp
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

public boolean exist(char[][] board, String word) {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (backtrack(board, word, r, c, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean backtrack(char[][] board, String word, int r, int c, int index) {
    if (index == word.length()) return true;
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) {
        return false;
    }

    // Choose & Mark
    char temp = board[r][c];
    board[r][c] = '#';

    // Explore
    boolean found = backtrack(board, word, r + 1, c, index + 1) ||
                    backtrack(board, word, r - 1, c, index + 1) ||
                    backtrack(board, word, r, c + 1, index + 1) ||
                    backtrack(board, word, r, c - 1, index + 1);

    // Unchoose & Unmark
    board[r][c] = temp;
    return found;
}

bool backtrack(vector<vector<char>>& board, const string& word, int r, int c, int index) {
    if (index == word.length()) return true;
    if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size() || board[r][c] != word[index]) {
        return false;
    }

    // Choose & Mark
    char temp = board[r][c];
    board[r][c] = '#';

    // Explore
    bool found = backtrack(board, word, r + 1, c, index + 1) ||
                 backtrack(board, word, r - 1, c, index + 1) ||
                 backtrack(board, word, r, c + 1, index + 1) ||
                 backtrack(board, word, r, c - 1, index + 1);

    // Unchoose & Unmark
    board[r][c] = temp;
    return found;
}

bool exist(vector<vector<char>>& board, string word) {
    for (int r = 0; r < board.size(); ++r) {
        for (int c = 0; c < board[0].size(); ++c) {
            if (backtrack(board, word, r, c, 0)) {
                return true;
            }
        }
    }
    return false;
}

Complexity Analysis

Time Complexity: $O(N * 3^L)$ , where N is the number of cells in the grid and L is the length of the word. For each cell, we initiate a search. The search can branch out to 3 neighbors (we don't go back to the cell we came from).
Space Complexity: $O(L)$ , where L is the length of the word. This is the maximum depth of the recursion stack.

Bonus Points: From Grids to Game AI

This exact "Choose, Explore, Unchoose" pattern is fundamental in artificial intelligence, especially for game-playing bots. An AI for a game like chess or checkers explores future moves by: