Word Search in Grid Using Backtracking in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result for a Simple Grid

What is the output of the following C# code that checks if the word "CAT" exists in the grid using backtracking?

DSA C#

using System;

class Program {
    static char[][] board = new char[][] {
        new char[] {'C', 'A', 'T'},
        new char[] {'X', 'Y', 'Z'},
        new char[] {'A', 'B', 'C'}
    };

    static bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
        bool[,] visited = new bool[rows, cols];

        bool Backtrack(int r, int c, int index) {
            if (index == word.Length) return true;
            if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
            if (visited[r, c] || board[r][c] != word[index]) return false;

            visited[r, c] = true;
            bool found = Backtrack(r + 1, c, index + 1) ||
                         Backtrack(r - 1, c, index + 1) ||
                         Backtrack(r, c + 1, index + 1) ||
                         Backtrack(r, c - 1, index + 1);
            visited[r, c] = false;
            return found;
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (Backtrack(i, j, 0)) return true;
            }
        }
        return false;
    }

    static void Main() {
        Console.WriteLine(Exist(board, "CAT"));
    }
}

A Runtime error

B True

C Compilation error

D False

💡 Hint

Think about whether the word "CAT" can be found by moving up, down, left, or right in the grid.

The word "CAT" is found in the first row of the grid from left to right, so the backtracking returns true.

❓ Predict Output

intermediate

Output of Word Search for Word Not Present

What is the output of the following C# code that checks if the word "DOG" exists in the grid using backtracking?

DSA C#

using System;

class Program {
    static char[][] board = new char[][] {
        new char[] {'C', 'A', 'T'},
        new char[] {'X', 'Y', 'Z'},
        new char[] {'A', 'B', 'C'}
    };

    static bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
        bool[,] visited = new bool[rows, cols];

        bool Backtrack(int r, int c, int index) {
            if (index == word.Length) return true;
            if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
            if (visited[r, c] || board[r][c] != word[index]) return false;

            visited[r, c] = true;
            bool found = Backtrack(r + 1, c, index + 1) ||
                         Backtrack(r - 1, c, index + 1) ||
                         Backtrack(r, c + 1, index + 1) ||
                         Backtrack(r, c - 1, index + 1);
            visited[r, c] = false;
            return found;
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (Backtrack(i, j, 0)) return true;
            }
        }
        return false;
    }

    static void Main() {
        Console.WriteLine(Exist(board, "DOG"));
    }
}

A True

B Compilation error

C Runtime error

D False

💡 Hint

Check if the letters D, O, G appear connected in the grid.

The word "DOG" is not present in the grid in any connected path, so the function returns false.

🧠 Conceptual

advanced

Understanding Backtracking Visited State Reset

Why is it important to reset the visited state (visited[r, c] = false) after exploring all directions in the backtracking function?

A To mark the cell as permanently unusable for the entire search

B To prevent the program from running into an infinite loop

C To allow the same cell to be used in different search paths for the word

D To optimize memory usage by clearing the visited array

💡 Hint

Think about how backtracking explores multiple paths and needs to reuse cells in different attempts.

Resetting visited allows the algorithm to try other paths that may use the same cell later, enabling full exploration.

🔧 Debug

advanced

Identify the Bug in Word Search Backtracking Code

What error will the following code produce when searching for the word "CAT"?

DSA C#

using System;

class Program {
    static char[][] board = new char[][] {
        new char[] {'C', 'A', 'T'},
        new char[] {'X', 'Y', 'Z'},
        new char[] {'A', 'B', 'C'}
    };

    static bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
        bool[,] visited = new bool[rows, cols];

        bool Backtrack(int r, int c, int index) {
            if (index == word.Length) return true;
            if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
            if (visited[r, c] || board[r][c] != word[index]) return false;

            visited[r, c] = true;
            bool found = Backtrack(r + 1, c, index + 1) ||
                         Backtrack(r - 1, c, index + 1) ||
                         Backtrack(r, c + 1, index + 1) ||
                         Backtrack(r, c - 1, index + 1);
            // Missing visited reset here
            return found;
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (Backtrack(i, j, 0)) return true;
            }
        }
        return false;
    }

    static void Main() {
        Console.WriteLine(Exist(board, "CAT"));
    }
}

A The code returns false even if the word exists

B The code causes a stack overflow due to infinite recursion

C The code throws an IndexOutOfRangeException

D The code returns true even if the word does not exist

💡 Hint

Check what happens if visited cells are never reset after recursion.

Without resetting visited, cells remain marked visited, blocking other paths and causing false negatives.

🚀 Application

expert

Count All Occurrences of a Word in Grid Using Backtracking

Given a grid and a word, how would you modify the backtracking algorithm to count all distinct occurrences of the word in the grid instead of just checking if it exists?

A Add a global counter and increment it each time the word is found; continue searching all paths without stopping

B Stop searching after the first occurrence is found to optimize performance

C Use a hash set to store visited cells permanently to avoid counting duplicates

D Only search from the first cell that matches the first letter of the word

💡 Hint

Think about how to explore all possible paths and keep track of how many times the word appears.

To count all occurrences, the algorithm must explore all paths and increment a counter each time the word is found.

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