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 of word?

No→Move to next cell

Yes↓

Mark cell as visited

↓

Explore neighbors (up, down, left, right)

↓

Does neighbor match next letter?

No→Backtrack: unmark cell

Yes↓

Repeat exploration for next letter

↓

All letters matched?

Yes→Return True

No↓

Backtrack: unmark cell and try other neighbors

↓

If all cells tried and no match

→Return False

The algorithm tries each cell as a start, then uses backtracking to explore neighbors matching the word letters step-by-step, marking visited cells to avoid reuse.

Execution Sample

DSA C#

bool Exist(char[][] board, string word) {
  for (int i = 0; i < board.Length; i++) {
    for (int j = 0; j < board[0].Length; j++) {
      if (Backtrack(board, word, 0, i, j)) return true;
    }
  }
  return false;
}

This code checks each cell in the grid as a start point and calls backtracking to find the word.

Execution Table

Step	Operation	Current Position (row,col)	Word Index	Visited Cells	Action	Visual State
1	Start at cell	(0,0)	0	{}	Check if board[0][0] == word[0]	Grid unchanged
2	Match found	(0,0)	0	{(0,0)}	Mark visited and explore neighbors	Visited: (0,0)
3	Explore neighbor	(0,1)	1	{(0,0)}	board[0][1] == word[1]? No	Visited: (0,0)
4	Explore neighbor	(1,0)	1	{(0,0)}	board[1][0] == word[1]? Yes	Visited: (0,0)
5	Mark visited	(1,0)	1	{(0,0),(1,0)}	Explore neighbors for next letter	Visited: (0,0),(1,0)
6	Explore neighbor	(2,0)	2	{(0,0),(1,0)}	board[2][0] == word[2]? Yes	Visited: (0,0),(1,0)
7	Mark visited	(2,0)	2	{(0,0),(1,0),(2,0)}	Explore neighbors for next letter	Visited: (0,0),(1,0),(2,0)
8	Explore neighbor	(3,0)	3	{(0,0),(1,0),(2,0)}	Out of bounds	Visited: (0,0),(1,0),(2,0)
9	Explore neighbor	(2,1)	3	{(0,0),(1,0),(2,0)}	board[2][1] == word[3]? No	Visited: (0,0),(1,0),(2,0)
10	Explore neighbor	(1,0)	3	{(0,0),(1,0),(2,0)}	Already visited	Visited: (0,0),(1,0),(2,0)
11	Explore neighbor	(2,-1)	3	{(0,0),(1,0),(2,0)}	Out of bounds	Visited: (0,0),(1,0),(2,0)
12	Backtrack	(2,0)	2	{(0,0),(1,0)}	Unmark (2,0), try other neighbors	Visited: (0,0),(1,0)
13	Explore neighbor	(1,1)	2	{(0,0),(1,0)}	board[1][1] == word[2]? No	Visited: (0,0),(1,0)
14	Backtrack	(1,0)	1	{(0,0)}	Unmark (1,0), try other neighbors	Visited: (0,0)
15	Explore neighbor	(0,1)	1	{(0,0)}	board[0][1] == word[1]? No	Visited: (0,0)
16	Explore neighbor	(-1,0)	1	{(0,0)}	Out of bounds	Visited: (0,0)
17	Backtrack	(0,0)	0	{}	Unmark (0,0), move to next cell	Visited: {}
18	Start at cell	(0,1)	0	{}	Check if board[0][1] == word[0]	Grid unchanged
19	No match	(0,1)	0	{}	Move to next cell	Grid unchanged
20	Start at cell	(0,2)	0	{}	Check if board[0][2] == word[0]	Grid unchanged
21	Match found	(0,2)	0	{(0,2)}	Mark visited and explore neighbors	Visited: (0,2)
22	Explore neighbor	(0,3)	1	{(0,2)}	board[0][3] == word[1]? Yes	Visited: (0,2)
23	Mark visited	(0,3)	1	{(0,2),(0,3)}	Explore neighbors for next letter	Visited: (0,2),(0,3)
24	Explore neighbor	(0,4)	2	{(0,2),(0,3)}	Out of bounds	Visited: (0,2),(0,3)
25	Explore neighbor	(1,3)	2	{(0,2),(0,3)}	board[1][3] == word[2]? Yes	Visited: (0,2),(0,3)
26	Mark visited	(1,3)	2	{(0,2),(0,3),(1,3)}	Explore neighbors for next letter	Visited: (0,2),(0,3),(1,3)
27	Explore neighbor	(2,3)	3	{(0,2),(0,3),(1,3)}	board[2][3] == word[3]? Yes	Visited: (0,2),(0,3),(1,3)
28	Mark visited	(2,3)	3	{(0,2),(0,3),(1,3),(2,3)}	All letters matched, return True	Visited: (0,2),(0,3),(1,3),(2,3)
29	Return	-	-	-	Word found in grid	Final Visited: (0,2),(0,3),(1,3),(2,3)

💡 Word found at step 28, backtracking returns True

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 12	After Step 14	After Step 17	After Step 21	After Step 23	After Step 26	After Step 28	Final
Visited Cells	{}	{(0,0)}	{(0,0),(1,0)}	{(0,0),(1,0),(2,0)}	{(0,0),(1,0)}	{(0,0)}	{}	{(0,2)}	{(0,2),(0,3)}	{(0,2),(0,3),(1,3)}	{(0,2),(0,3),(1,3),(2,3)}	{(0,2),(0,3),(1,3),(2,3)}
Current Position	(0,0)	(0,0)	(1,0)	(2,0)	(2,0)	(1,0)	(0,0)	(0,2)	(0,3)	(1,3)	(2,3)	(2,3)
Word Index	0	0	1	2	2	1	0	0	1	2	3	3

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 and incorrect matches. See steps 2, 5, and 7 where cells are marked, and steps 12 and 14 where backtracking unmarks them.

What happens when a neighbor cell is out of grid bounds?

The algorithm skips out-of-bound neighbors immediately without marking or exploring further. This is shown in steps 8 and 11 where positions like (3,0) and (2,-1) are out of bounds.

How does the algorithm know when the word is fully matched?

When the word index reaches the last letter and a matching cell is found, the algorithm returns true immediately, as in step 28 where all letters matched and the search ends.

Visual Quiz - 3 Questions

Look at the execution table, what is the set of visited cells after step 7?

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

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

C {(0,0)}

D {}

💡 Hint

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

At which step does the algorithm backtrack from cell (2,0)?

A Step 10

B Step 12

C Step 14

D Step 17

💡 Hint

Look for the step where (2,0) is unmarked in the 'Visited Cells' column.

If the word's first letter did not match at (0,0), what would be the next step?

A Start at cell (0,1)

B Return false immediately

C Start at cell (1,0)

D Mark (0,0) as visited anyway

💡 Hint

Refer to steps 1 and 19 where the algorithm moves to the next cell after no match.

Concept Snapshot

Word Search using Backtracking:
- Start from each cell in grid
- Check if cell matches current word letter
- Mark cell visited to avoid reuse
- Recursively explore neighbors (up, down, left, right)
- Backtrack by unmarking if path fails
- Return true if all letters matched
- Return false if no path found

Full Transcript

This visualization shows how the word search algorithm uses backtracking to find a word in a grid. It starts at each cell, checks if the letter matches the first letter of the word, then marks the cell as visited. It explores neighbors recursively for the next letters, marking and unmarking cells as it goes. If it reaches the end of the word, it returns true. If no path matches, it backtracks and tries other paths or cells. The execution table tracks each step, the current position, visited cells, and actions taken. Key moments explain why marking visited cells is important, how out-of-bounds neighbors are handled, and how the algorithm detects a full match. The quiz tests understanding of visited cells, backtracking steps, and next moves when letters don't match.

Practice

1. What is the main purpose of backtracking in the Word Search problem on a grid?

easy

A. To count the number of words in the grid

B. To sort the grid alphabetically

C. To explore all possible paths to find the word

D. To replace characters in the grid

Solution

1. Step 1: Understand backtracking role

   Backtracking tries all possible paths in the grid to find the target word by moving in allowed directions.

2. Step 2: Eliminate other options

   Sorting, counting, or replacing characters are unrelated to the search process using backtracking.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking explores paths step-by-step to find the word [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with counting words
• Assuming backtracking replaces characters permanently

2. Which of the following is the correct way to check if the next cell is within grid bounds in C#?

easy

A. if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length)

B. if (row > 0 && row <= grid.Length && col > 0 && col <= grid[0].Length)

C. if (row >= 0 && row <= grid.Length && col >= 0 && col <= grid[0].Length)

D. if (row > 0 && row < grid.Length && col > 0 && col < grid[0].Length)

Solution

1. Step 1: Understand grid indexing in C#

   Grid rows and columns are zero-indexed, so valid indices are from 0 to Length-1.

2. Step 2: Check boundary conditions

   if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length) correctly checks if row and col are >= 0 and less than Length, ensuring valid indices.

3. Final Answer:

   if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length) -> Option A

4. Quick Check:

   Bounds check uses >=0 and < Length [OK]

Hint: Use >=0 and < Length for zero-based index checks [OK]

Common Mistakes:

• Using > 0 excludes first row/column
• Using <= Length causes out-of-range errors
• Confusing row and column length checks

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

char[][] grid = {
  new char[] {'A','B','C','E'},
  new char[] {'S','F','C','S'},
  new char[] {'A','D','E','E'}
};
string word = "ABCCED";
bool result = WordSearch(grid, word);
Console.WriteLine(result);

Assuming WordSearch uses backtracking correctly to find the word in the grid.

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze the grid and word

   The word "ABCCED" can be found by moving right and down starting at grid[0][0]: A->B->C->C->E->D.

2. Step 2: Confirm backtracking finds the word

   Backtracking explores all paths and will find this sequence, so result is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Word found in grid = True [OK]

Hint: Trace word path step-by-step in grid to confirm presence [OK]

Common Mistakes:

• Assuming word is not found without tracing path
• Confusing similar letters in grid
• Ignoring backtracking's ability to explore all paths

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

bool Backtrack(char[][] grid, string word, int index, int row, int col) {
  if (index == word.Length) return true;
  if (row < 0 || row >= grid.Length || col < 0 || col >= grid[0].Length) return false;
  if (grid[row][col] != word[index]) return false;
  char temp = grid[row][col];
  grid[row][col] = '#';
  bool found = Backtrack(grid, word, index + 1, row + 1, col) ||
               Backtrack(grid, word, index + 1, row - 1, col) ||
               Backtrack(grid, word, index + 1, row, col + 1) ||
               Backtrack(grid, word, index + 1, row, col - 1);
  grid[row][col] = temp;
  return found;
}

medium

A. The grid cell is not restored after recursion

B. The function does not check for visited cells properly

C. The base case should check index > word.Length

D. The function does not check grid boundaries before accessing

Solution

1. Step 1: Check visited cell marking

   The code marks visited cells by replacing with '#', which prevents revisiting during recursion.

2. Step 2: Identify missing visited check

   However, the code does not check if the current cell is '#' before comparing with word[index], so it may revisit marked cells incorrectly.

3. Final Answer:

   The function does not check for visited cells properly -> Option B

4. Quick Check:

   Visited check missing = Bug [OK]

Hint: Always check if cell is visited before matching character [OK]

Common Mistakes:

• Forgetting to check if cell is marked visited
• Incorrect base case condition
• Not restoring grid cell after recursion

5. Given a 4x4 grid:

char[][] grid = {
  new char[] {'C','A','T','F'},
  new char[] {'B','G','E','S'},
  new char[] {'I','T','A','E'},
  new char[] {'S','O','N','G'}
};

Which of the following words cannot be found using backtracking moving only up, down, left, or right?

hard

A. "CAT"

B. "GATE"

C. "SONG"

D. "BATS"

Solution

1. Step 1: Check presence of each word

   "CAT" is in first row (C->A->T). "SONG" is in last row (S->O->N->G). "GATE" can be formed by G->A->T->E in middle rows.

2. Step 2: Verify "BATS" formation

   "BATS" requires B->A->T->S. B is at grid[1][0], but no path connects A and T and then S in sequence moving only up/down/left/right without skipping letters.

3. Final Answer:

   "BATS" cannot be found -> Option D

4. Quick Check:

   Word path missing = "BATS" [OK]

Hint: Trace each letter path carefully to confirm word presence [OK]

Common Mistakes:

• Assuming all words are present without path check
• Ignoring movement restrictions (no diagonals)
• Confusing letter positions in grid