Word Search in Grid Using Backtracking in DSA Python - Execution Trace

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter of word?

No→Move to next cell

Yes↓

Mark cell as visited

↓

Explore neighbors (up, down, left, right)

↓

For each neighbor: matches next letter?

Yes↓

Recurse from neighbor

↓

If full word found

→Return True

No↓

Backtrack: unmark cell

↓

Try next neighbor or next cell

↓

If all cells tried and no match

→Return False

Start from each cell, check if it matches the word's first letter, then explore neighbors recursively using backtracking until the word is found or all options are exhausted.

Execution Sample

DSA Python

def exist(board, word):
    def backtrack(r, c, i):
        if i == len(word): return True
        if r<0 or c<0 or r>=len(board) or c>=len(board[0]) or board[r][c]!=word[i]: return False
        temp = board[r][c]
        board[r][c] = '#'
        res = any(backtrack(r+dr, c+dc, i+1) for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)])
        board[r][c] = temp
        return res
    return any(backtrack(r,c,0) for r in range(len(board)) for c in range(len(board[0])))

This code checks if a word exists in a 2D grid by trying each cell as a start and using backtracking to find the word.

Execution Table

Step	Operation	Current Position (r,c)	Index in Word (i)	Visited Cells	Visual State of Board	Action/Result
1	Start search	-	-	{}	[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]	Try cell (0,0) for 'A'
2	Match first letter	(0,0)	0	{(0,0)}	[['#','B','C','E'],['S','F','C','S'],['A','D','E','E']]	Mark (0,0) visited, look for 'B' next
3	Explore neighbors	(1,0)	1	{(0,0)}	[['#','B','C','E'],['S','F','C','S'],['A','D','E','E']]	Cell (1,0)='S' != 'B', backtrack
4	Explore neighbors	(0,1)	1	{(0,0),(0,1)}	[['#','B','C','E'],['S','F','C','S'],['A','D','E','E']]	Cell (0,1)='B' matches 'B', continue
5	Explore neighbors	(0,2)	2	{(0,0),(0,1),(0,2)}	[['#','#','C','E'],['S','F','C','S'],['A','D','E','E']]	Cell (0,2)='C' matches 'C', continue
6	Explore neighbors	(0,3)	3	{(0,0),(0,1),(0,2),(0,3)}	[['#','#','#','E'],['S','F','C','S'],['A','D','E','E']]	Cell (0,3)='E' matches 'E', continue
7	Explore neighbors	(1,3)	4	{(0,0),(0,1),(0,2),(0,3)}	[['#','#','#','#'],['S','F','C','S'],['A','D','E','E']]	i == len(word), return True
8	Return True	-	-	-	[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]	Word found, stop search

💡 Word found at step 7, backtracking returns True and search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 6	After Step 7	Final
r	-	0	0	0	0	1	-
c	-	0	1	2	3	3	-
i	-	0	1	2	3	4	-
Visited Cells	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(0,2)}	{(0,0),(0,1),(0,2),(0,3)}	{(0,0),(0,1),(0,2),(0,3)}	-
Board State	[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]	[['#','B','C','E'],['S','F','C','S'],['A','D','E','E']]	[['#','B','C','E'],['S','F','C','S'],['A','D','E','E']]	[['#','#','C','E'],['S','F','C','S'],['A','D','E','E']]	[['#','#','#','E'],['S','F','C','S'],['A','D','E','E']]	[['#','#','#','#'],['S','F','C','S'],['A','D','E','E']]	[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]

Key Moments - 3 Insights

Why do we mark a cell as visited by changing its value to '#'?

Marking the cell as '#' prevents revisiting the same cell in the current path, avoiding infinite loops. See step 2 in execution_table where (0,0) is marked before exploring neighbors.

Why do we backtrack by restoring the cell's original value after exploring neighbors?

Restoring the cell allows other paths to use it for different search attempts. This is shown in variable_tracker where the board state returns to original after the search ends.

Why do we check boundaries and character match before recursion?

To avoid invalid positions and wrong letters, ensuring only valid paths are explored. Step 3 shows skipping cell (1,0) because letter doesn't match.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the set of visited cells?

A {(0,0),(0,1)}

B {(0,0),(1,0)}

C {(0,1)}

D {}

💡 Hint

Check the 'Visited Cells' column at step 4 in execution_table.

At which step does the algorithm find the full word?

A Step 5

B Step 7

C Step 3

D Step 2

💡 Hint

Look at the 'Action/Result' column for when the word is found.

If we did not mark cells as visited, what would happen?

A The algorithm would run faster

B The word would be found immediately

C The algorithm might revisit cells causing infinite loops

D The board would be unchanged

💡 Hint

Refer to key_moments about marking cells as visited to avoid revisiting.

Concept Snapshot

Word Search using Backtracking:
- Start from each cell in grid
- Check if cell matches current word letter
- Mark cell visited (e.g., '#') to avoid reuse
- Recursively explore neighbors (up, down, left, right)
- Backtrack by restoring cell after exploring
- Return True if full word matched, else False

Full Transcript

This visualization shows how to find a word in a 2D grid using backtracking. We start from each cell and check if it matches the first letter of the word. If yes, we mark it visited by replacing the letter with '#'. Then we explore neighbors recursively for the next letter. If a neighbor doesn't match or is out of bounds, we backtrack by restoring the cell's original letter. This process continues until the full word is found or all paths are tried. The execution table tracks each step, showing the current position, visited cells, board state, and actions. Key moments explain why marking visited cells and backtracking are important to avoid loops and allow multiple search paths. The quiz tests understanding of visited cells, when the word is found, and the importance of marking visited cells.

Practice

1. What is the main purpose of using backtracking in a word search grid problem?

easy

A. To count the number of words in the grid

B. To sort the grid alphabetically

C. To replace characters in the grid

D. To explore all possible paths to find the word

Solution

1. Step 1: Understand backtracking in word search

   Backtracking tries all possible paths in the grid to find the target word by exploring neighbors recursively.

2. Step 2: Eliminate unrelated options

   Sorting, counting words, or replacing characters are not related to backtracking's purpose in this problem.

3. Final Answer:

   To explore all possible paths to find the word -> Option D

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking means trying all paths step-by-step [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with simple searching
• Ignoring the recursive exploration nature

2. Which of the following is the correct way to check if a position (row, col) is inside the grid boundaries in Python?

easy

A. if 0 <= row < len(grid) and 0 <= col < len(grid[0]):

B. if row > 0 and col > 0 and row < len(grid) and col < len(grid[0]):

C. if row <= len(grid) and col <= len(grid[0]):

D. if row >= 0 or col >= 0:

Solution

1. Step 1: Understand grid boundary conditions

   Valid indices must be greater or equal to 0 and less than the number of rows or columns.

2. Step 2: Analyze each option

   if 0 <= row < len(grid) and 0 <= col < len(grid[0]): correctly uses inclusive lower bound and exclusive upper bound checks. if row > 0 and col > 0 and row < len(grid) and col < len(grid[0]): excludes 0 index, which is invalid. if row <= len(grid) and col <= len(grid[0]): allows equal to length, which is out of range. if row >= 0 or col >= 0: uses 'or' which is incorrect logic.

3. Final Answer:

   if 0 <= row < len(grid) and 0 <= col < len(grid[0]): -> Option A

4. Quick Check:

   Boundary check = if 0 <= row < len(grid) and 0 <= col < len(grid[0]): [OK]

Hint: Use 0 <= index < length for valid grid positions [OK]

Common Mistakes:

• Using > 0 instead of >= 0 excludes first row/column
• Allowing index equal to length causes errors
• Using 'or' instead of 'and' in conditions

3. What will be the output of the following code snippet?

grid = [['A','B','C','E'],
        ['S','F','C','S'],
        ['A','D','E','E']]
word = "ABCCED"

# Function to check word existence
result = word_search(grid, word)
print(result)

# Assume word_search uses backtracking to find the word

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Understand the word and grid

   The word "ABCCED" can be found by moving right and down in the grid starting at grid[0][0].

2. Step 2: Confirm backtracking finds the word

   Backtracking explores neighbors and matches letters sequentially, so it returns True if the word exists.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Word found = True [OK]

Hint: Trace letters stepwise to confirm word presence [OK]

Common Mistakes:

• Assuming word is not found without tracing
• Confusing output with None or error
• Ignoring backtracking's path exploration

4. Identify the bug in this backtracking snippet for word search:

def backtrack(r, c, index):
    if index == len(word):
        return True
    if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != word[index]:
        return False
    temp = grid[r][c]
    grid[r][c] = '#'
    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))
    grid[r][c] = temp
    return found

medium

A. Using '#' as marker can conflict with grid letters

B. Missing base case for index == 0

C. No bug; code is correct

D. Modifying grid in place without restoring causes errors

Solution

1. Step 1: Analyze the backtracking logic

   The code marks visited cells with '#', explores neighbors recursively, and restores the cell after exploration.

2. Step 2: Check for bugs

   Restoring the cell after recursion prevents errors. Base case for index == len(word) is correct. '#' is a common marker and safe if not in original grid.

3. Final Answer:

   No bug; code is correct -> Option C

4. Quick Check:

   Code logic = Correct [OK]

Hint: Check if visited cells are restored after recursion [OK]

Common Mistakes:

• Forgetting to restore grid cell after recursion
• Adding unnecessary base cases
• Assuming marker conflicts without checking grid content

5. Given a 4x4 grid and a list of words, which approach best finds all words using backtracking efficiently? A) Run backtracking separately for each word on the entire grid. B) Sort words alphabetically and search in order. C) Search only the first letter of each word and stop. D) Build a Trie of words and backtrack once to find all words simultaneously.

hard

A. Run backtracking separately for each word on the entire grid.

B. Build a Trie of words and backtrack once to find all words simultaneously.

C. Search only the first letter of each word and stop.

D. Sort words alphabetically and search in order.

Solution

1. Step 1: Understand the problem of multiple words

   Running backtracking separately for each word is inefficient because it repeats searches.

2. Step 2: Use Trie to optimize search

   Building a Trie of all words allows a single backtracking pass to find all words by prefix matching, improving efficiency.

3. Step 3: Eliminate other options

   Searching only first letters or sorting words does not improve search efficiency significantly.

4. Final Answer:

   Build a Trie of words and backtrack once to find all words simultaneously. -> Option B

5. Quick Check:

   Trie + backtracking = Efficient multi-word search [OK]

Hint: Use Trie to find multiple words in one backtracking pass [OK]

Common Mistakes:

• Running backtracking repeatedly wastes time
• Ignoring prefix sharing among words
• Assuming sorting helps search efficiency