Word Search in Grid: 2D Array Backtracking Problem Explained with Examples

Word Search in Grid is one of the most popular backtracking problems asked in coding interviews. This problem tests your understanding of recursion, 2D array manipulation, and efficient search strategies. It resembles real-world word puzzles such as crosswords or word hunts you might solve in newspapers or puzzle apps.

In this article, we will explore:

Understanding the Word Search problem
Backtracking approach in a 2D array
Step-by-step algorithm explanation
Visual walkthrough with grids and directions
Python implementation with detailed comments
Complexity analysis (time and space)

Table of Contents

Understanding the Word Search Problem

The problem statement is usually defined as follows:

You are given a 2D board of characters and a word. Check if the word can be constructed from the letters in the grid. You can move up, down, left, or right, and the same cell cannot be reused in a single word path.

Example:

Board =
[
  ['C','A','T'],
  ['R','A','T'],
  ['D','O','G']
]

Word = "CAT"

The word “CAT” can be found in the first row going left to right.

Visual Representation of Word Formation

Let’s visualize how the algorithm explores paths in the grid.

In this diagram, the algorithm starts at cell [0,0] (“C”), moves right to [0,1] (“A”), then right again to [0,2] (“T”). This forms the target word “CAT”.

Backtracking Approach

The backtracking solution works as follows:

Iterate over every cell in the board.
Whenever the first character matches the starting letter of the word, perform DFS (Depth First Search).
At each step, move in all four directions — up, down, left, right.
Mark the cell as visited to avoid revisiting it in the current path by temporarily modifying the board or maintaining a visited matrix.
If the entire word is found, return True.
If not possible, backtrack and try other moves.

Python Implementation


def exist(board, word):
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, index):
        # If all characters are found
        if index == len(word):
            return True
        
        # Check boundaries and character match
        if (r < 0 or c < 0 or r >= rows or c >= cols 
            or board[r][c] != word[index]):
            return False
        
        # Mark as visited using temporary character
        temp = board[r][c]
        board[r][c] = "#"

        # Explore all directions
        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))

        # Restore the cell
        board[r][c] = temp

        return found

    # Try starting from each cell
    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False


# Example usage
grid = [
  ["C","A","T"],
  ["R","A","T"],
  ["D","O","G"]
]

print(exist(grid, "CAT"))  # True
print(exist(grid, "DOG"))  # True
print(exist(grid, "CART")) # True
print(exist(grid, "COW"))  # False

Step-by-Step Execution Example

Suppose the word is “CART”:

Grid =
C A T
R A T
D O G

Start at [0,0]: “C”
Move down to [1,0]: “R”
Move right to [1,1]: “A”
Move right to [1,2]: “T”

Word “CART” is found.

Interactive Visualization Idea

You can create an interactive grid where users manually click paths to form words. In a web page, this could be implemented with JavaScript highlighting visited cells. This helps beginners understand backtracking more intuitively. For this article, we’ll illustrate with static visuals.

Complexity Analysis

The complexity of backtracking solutions is as follows:

Time Complexity: O(N * M * 4^L) where N and M are rows and columns of the grid, and L is the length of the word. The factor 4^L arises because in the worst case, we explore 4 directions at each step.
Space Complexity: O(L) for recursion stack, since at most the call depth equals the word’s length. Additionally, O(1) extra space if we use in-place marking.

Applications

This algorithm concept is widely applicable:

Implementing real-world Word Puzzle solvers
AI-powered crossword generators
Graph traversal problems that use recursion and backtracking
Pathfinding in games and robotics

Conclusion

The Word Search in Grid problem is a classic example of using backtracking with 2D arrays. By carefully exploring directions, marking visited cells, and restoring states when backtracking, we can solve even complex searches.

Practice implementing the solution on different boards and words to deeply strengthen your recursion and backtracking skills. Mastery of this algorithm will make advanced grid-based algorithm problems much easier for you.