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

Concept Flow - Word Search in Grid Using Backtracking

Start at each cell in grid

↓

Check if cell matches first letter

↓

If match: Explore neighbors (up, down, left, right)

↓

Mark cell as visited

↓

Recursively check next letter in neighbors

↓

If all letters matched -> Success

↓

If dead end -> Backtrack (unmark cell)

↓

Try next neighbor or next start cell

↓

End: Word found or all cells tried

The algorithm tries each cell as a start, then explores neighbors recursively to match the word letters, backtracking when stuck.

Execution Sample

DSA C

bool exist(char** board, int rows, int cols, char* word) {
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (backtrack(board, rows, cols, word, i, j, 0)) return true;
    }
  }
  return false;
}

This code tries each cell as a start and calls backtrack to find the word recursively.

Execution Table

Step	Operation	Current Cell (row,col)	Word Index	Visited Cells	Action	Visual State
1	Start search	-	-	{}	Check cell (0,0)	[A][B][C] [D][E][F] [G][H][I]
2	Match first letter 'A'	(0,0)	0	{(0,0)}	Mark visited, check neighbors for 'B'	[*A][B][C] [D][E][F] [G][H][I]
3	Check neighbor (0,1)	(0,1)	1	{(0,0),(0,1)}	Match 'B', continue	[*A][*B][C] [D][E][F] [G][H][I]
4	Check neighbor (0,2)	(0,2)	2	{(0,0),(0,1),(0,2)}	Match 'C', continue	[*A][*B][*C] [D][E][F] [G][H][I]
5	Word complete	-	3	{(0,0),(0,1),(0,2)}	All letters matched	[*A][*B][*C] [D][E][F] [G][H][I]
6	Return success	-	-	-	Stop search	[*A][*B][*C] [D][E][F] [G][H][I]

💡 Word found at cells (0,0) -> (0,1) -> (0,2), all letters matched

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
Current Cell	-	(0,0)	(0,1)	(0,2)	-	-
Word Index	0	0	1	2	3	3
Visited Cells	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(0,2)}	{(0,0),(0,1),(0,2)}	{(0,0),(0,1),(0,2)}
Action	Start	Mark (0,0)	Mark (0,1)	Mark (0,2)	Complete	Stop

Key Moments - 3 Insights

Why do we mark cells as visited during backtracking?

Marking cells as visited prevents revisiting the same cell in the current path, avoiding infinite loops. See Step 2 and Step 3 where cells are marked before exploring neighbors.

What happens if a neighbor cell does not match the next letter?

The algorithm backtracks by unmarking the current cell and tries other neighbors or start cells. This is implied after Step 4 if no match is found, but in this example, all letters matched.

Why do we try every cell as a starting point?

Because the word can start anywhere in the grid, the algorithm tries all cells to ensure no possible start is missed. This is shown in Step 1 where search begins at (0,0).

Visual Quiz - 3 Questions

Look at the execution table, what is the set of visited cells at Step 3?

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

B {(0,1)}

C {(0,0)}

D {}

💡 Hint

Check the 'Visited Cells' column at Step 3 in the execution_table.

At which step does the algorithm confirm the word is fully matched?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

Look for the 'Word complete' operation in the execution_table.

If the first letter did not match at (0,0), what would happen next?

A Backtrack and try neighbors of (0,0)

B Try next cell (0,1) as start

C Stop search immediately

D Mark (0,0) as visited anyway

💡 Hint

Refer to the concept_flow where each cell is tried as a start if no match.

Concept Snapshot

Word Search using Backtracking:
- Start from each cell in grid
- Check if cell matches current letter
- Mark cell visited and explore neighbors (up, down, left, right)
- Recursively match next letter
- Backtrack if no match
- Success if all letters matched

Full Transcript

This visualization shows how the word search algorithm uses backtracking to find a word in a grid. It starts from each cell, checks if the letter matches the first letter of the word, then recursively explores neighbors for the next letters. Cells are marked visited to avoid reuse in the same path. If a path fails, it backtracks by unmarking cells and tries other paths. The execution table tracks each step, showing current cell, word index, visited cells, and the grid state. Key moments clarify why marking visited is important, how backtracking works, and why all cells are tried as start points. The quiz tests understanding of visited cells, completion step, and search flow. The snapshot summarizes the backtracking approach in simple steps.

Practice

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

easy

A. To sort the grid alphabetically before searching

B. To explore all possible paths to find the word in the grid

C. To count the number of words in the grid

D. To replace characters in the grid with a placeholder

Solution

1. Step 1: Understand backtracking in grid search

   Backtracking tries all possible paths from a starting point to find the target word.

2. Step 2: Compare options with backtracking purpose

   Only To explore all possible paths to find the word in the grid describes exploring all paths, which matches backtracking's goal.

3. Final Answer:

   To explore all possible paths to find the word in the grid -> Option B

4. Quick Check:

   Backtracking = explore all paths [OK]

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

Common Mistakes:

• Thinking backtracking sorts or counts words
• Confusing backtracking with simple search
• Assuming backtracking modifies the grid permanently

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

easy

A. if (row >= 1 && row < rows && col >= 1 && col < cols)

B. if (row > 0 && row <= rows && col > 0 && col <= cols)

C. if (row > 0 && row < rows && col >= 0 && col <= cols)

D. if (row >= 0 && row < rows && col >= 0 && col < cols)

Solution

1. Step 1: Understand zero-based indexing in C arrays

   Arrays start at index 0, so valid indices are from 0 to rows-1 and 0 to cols-1.

2. Step 2: Check each option for correct boundary conditions

   if (row >= 0 && row < rows && col >= 0 && col < cols) correctly uses >= 0 and < rows/cols. Others use > 0 or <= rows which are incorrect for zero-based arrays.

3. Final Answer:

   if (row >= 0 && row < rows && col >= 0 && col < cols) -> Option D

4. Quick Check:

   Check boundaries with >=0 and < size [OK]

Hint: Use zero-based index: start at 0, less than size [OK]

Common Mistakes:

• Using > 0 instead of >= 0 excludes first row/column
• Using <= rows includes out-of-bound index
• Mixing 1-based and 0-based indexing

3. What will be the output of the following C code snippet for word search backtracking?

char grid[3][3] = {{'A','B','C'},{'D','E','F'},{'G','H','I'}};
int found = searchWord(grid, 3, 3, "BEF");
printf("%d", found);

Assuming searchWord correctly implements backtracking to find the word in the grid.

medium

A. 1

B. 0

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze the grid and the word "BEF"

   The grid rows are: ABC, DEF, GHI. The word "BEF" requires letters B, E, F in sequence adjacent horizontally or vertically.

2. Step 2: Check if "BEF" exists in adjacent cells

   B is at (0,1), E is at (1,1), F is at (1,2). B to E is vertical down, E to F is horizontal right, so path exists.

3. Step 3: Confirm if backtracking finds the word

   Backtracking can follow B(0,1) -> E(1,1) -> F(1,2), so word is found.

4. Final Answer:

   1 -> Option A

5. Quick Check:

   Word found = 1 [OK]

Hint: Trace letters stepwise in grid adjacency [OK]

Common Mistakes:

• Assuming letters must be in same row only
• Ignoring vertical or diagonal adjacency rules
• Confusing output 0 and 1 meaning

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

bool dfs(char grid[][], int row, int col, int index, char* word) {
  if (index == strlen(word)) return true;
  if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
  if (grid[row][col] != word[index]) return false;
  char temp = grid[row][col];
  grid[row][col] = '#';
  bool found = dfs(grid, row+1, col, index+1, word) ||
               dfs(grid, row-1, col, index+1, word) ||
               dfs(grid, row, col+1, index+1, word) ||
               dfs(grid, row, col-1, index+1, word);
  grid[row][col] = temp;
  return found;
}

medium

A. The base case should check index > strlen(word) instead of ==

B. The grid cell is not restored after recursion

C. The grid parameter lacks column size, causing compilation error

D. The function does not check diagonal neighbors

Solution

1. Step 1: Check function parameter declaration

   In C, 2D arrays must have fixed column size in parameters, e.g., char grid[][cols]. Missing column size causes compilation error.

2. Step 2: Verify other parts of the code

   Base case with index == strlen(word) is correct. Grid cell is restored after recursion. Diagonal check is optional, not a bug.

3. Final Answer:

   The grid parameter lacks column size, causing compilation error -> Option C

4. Quick Check:

   2D array params need column size [OK]

Hint: Always specify column size in 2D array parameters [OK]

Common Mistakes:

• Ignoring 2D array parameter syntax in C
• Thinking base case condition is wrong
• Assuming diagonal moves are mandatory

5. Given a 4x4 grid:

{ {'C','A','T','F'},
  {'B','G','E','S'},
  {'I','T','A','E'},
  {'S','O','N','G'} }

Which of the following words can be found using backtracking with adjacent horizontal or vertical moves only?

hard

A. "SONG"

B. "BATS"

C. "CATS"

D. "FATE"

Solution

1. Step 1: Check each word's presence in the grid with adjacency rules

   "SONG": S(3,0), O(3,1), N(3,2), G(3,3) - all adjacent horizontally, so possible.
   "BATS": B(1,0) has no adjacent A (neighbors: C(0,0), I(2,0), G(1,1)), so no.
   "CATS": C(0,0), A(0,1), T(0,2) adjacent, but T(0,2) has no adjacent S (neighbors: A(0,1), F(0,3), E(1,2), A(2,2)), so no.
   "FATE": F(0,3) has no adjacent A (neighbors: T(0,2), S(1,3)), so no.

2. Step 2: Identify which word is fully connected by adjacent moves

   Only "SONG" has all letters adjacent in sequence.

3. Final Answer:

   "SONG" -> Option A

4. Quick Check:

   Check adjacency path for each word [OK]

Hint: Trace letters stepwise horizontally or vertically [OK]

Common Mistakes:

• Assuming diagonal moves allowed
• Ignoring adjacency between letters
• Choosing words with missing adjacent letters