Backtracking for Grid Problems

1. The Core Idea: Exploring a Grid

Imagine you're in a maze and need to find a path from a starting point to an exit. You can move up, down, left, or right, but you can't walk through walls.

How would you solve this? You'd likely try one direction, follow it for a while, and if you hit a dead end or go in circles, you'd retrace your steps to the last intersection and try a different direction. This is exactly what backtracking does.

The key challenges in grid problems are:

1. Staying within bounds of the grid.
2. Avoiding obstacles (like the black cells in the image).
3. Not revisiting the same cell in the current path, which would cause an infinite loop (e.g., moving right from cell A to B, then left from B to A, and so on).

2. The "Mark and Unmark" Strategy

In the N-Queens problem, our state was global (the occupied columns and diagonals). Here, our state is tied to the current path. To avoid getting stuck in loops, we need to keep track of the cells we've already visited in the path we are currently exploring.

The standard way to do this is to mark a cell as visited when we step on it. Then, we explore its neighbors. When we're done exploring from that cell and are about to "step back" (i.e., when the recursive call returns), we must unmark it.

Why do we unmark? Because that cell, while a dead end for the current path, might be a perfectly valid part of a different path we explore later. This is the most crucial part of grid-based backtracking.

Let's watch a video that explains this concept in detail. It starts with a simple maze and builds up to the full backtracking solution, clarifying why we need to restore the state.

To summarize the key insight from the video:

• When moving forward into a cell (r, c): Mark (r, c) as visited so you don't step on it again in the same path. This is your choice.
• Explore neighbors: Recursively call your function for adjacent valid cells. This is the exploration.
• When moving backward from (r, c) (i.e., after all its neighbors have been explored and the function call for (r, c) is about to end): Unmark (r, c) by restoring its original state. This is the unchoose or backtracking step. It allows other paths to use this cell later.

This idea is also described well in the article "79. Word Search - In-Depth Explanation", which refers to it as leaving and picking up "breadcrumbs".

3. Application: The Word Search Problem

Now let's apply this pattern to a classic, high-ROI interview problem: Word Search (LeetCode #79).

Problem: Given an m x n grid of characters and a string word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

This is a perfect fit for our pattern:

• The Grid: The character board.
• The Path: The sequence of characters forming the word.
• The Constraint: The character at the current cell must match the next character in the word, and we cannot reuse cells.

We'll start a search from every cell in the grid. For each starting cell, we'll use a recursive backtracking function to see if we can spell the word from there.

The following video from NeetCode gives a concise, interview-oriented walkthrough of the solution.

4. The General Code Pattern for Grid Backtracking

Let's formalize the pattern we've learned. The approach for most grid-based backtracking problems can be summarized with the following template. The article "Master Backtracking Patterns" provides a fantastic summary of this.

Here's the generalized Python code structure based on what we've seen:

def solve_grid_problem(board):
    rows, cols = len(board), len(board[0])
    # A set to keep track of visited cells in the current path.
    # Alternatively, you can modify the board in-place.
    path = set() 

    def backtrack(r, c, /* other state variables */):
        # 1. Base Case for Success
        if (/* goal is met */):
            return True

        # 2. Base Cases for Failure (Pruning)
        if (r < 0 or r >= rows or c < 0 or c >= cols or # Out of bounds
            (r, c) in path or                           # Already visited
            not /* cell is valid for current step */):   # Obstacle or wrong char
            return False

        # 3. Choose
        path.add((r, c)) # Mark as visited for the current path

        # 4. Explore Neighbors (up, down, left, right)
        found = (backtrack(r + 1, c, ...) or
                 backtrack(r - 1, c, ...) or
                 backtrack(r, c + 1, ...) or
                 backtrack(r, c - 1, ...))

        # 5. Unchoose (Backtrack)
        path.remove((r, c)) # Unmark for future paths

        return found

    # Main loop to start the search from every possible starting cell
    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, /* initial state */):
                return True # Found a solution
    
    return False # No solution found

Complexity Analysis (for Word Search)

• Time Complexity: O(N * M * 4^L), where N x M is the size of the grid and L is the length of the word. We might start a search from each of the N * M cells. From each cell, the search can branch out in up to 4 directions (or 3, since we don't go back immediately), for L steps.
• Space Complexity: O(L) due to the depth of the recursion stack. If we use an explicit path set, it also takes O(L) space. If we modify the board in-place, the auxiliary space complexity is just the recursion stack depth.

Conclusion

In this lesson, you've extended your backtracking skills to grid traversal problems. You learned the critical importance of managing path-specific state and the "mark and unmark" technique to correctly explore all possibilities without getting stuck.

Key Takeaways:

• Grid-based problems are a common application of backtracking, often involving finding a valid path.
• The key challenge is preventing infinite loops and reusing cells within a single path.
• The solution is to mark cells as visited as you explore a path and, crucially, unmark them when you backtrack.
• This "Choose, Explore, Unchoose" pattern translates to "Mark, Recurse on Neighbors, Unmark" in grid problems.
• You can manage the visited state either by modifying the board in-place (space-efficient) or by using a separate hash set.

In our next lesson, we will tackle a common issue in recursion: overlapping subproblems. We'll introduce memoization, a powerful optimization technique where you cache the results of expensive function calls. This will serve as the perfect bridge from pure recursion to our next major module: Dynamic Programming.