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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search Result

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

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define ROWS 3
#define COLS 4

bool dfs(char grid[ROWS][COLS], int r, int c, const char *word, int index, bool visited[ROWS][COLS]) {
    if (index == strlen(word)) return true;
    if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
    if (visited[r][c] || grid[r][c] != word[index]) return false;

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

bool exist(char grid[ROWS][COLS], const char *word) {
    bool visited[ROWS][COLS] = {false};
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (dfs(grid, i, j, word, 0, visited)) return true;
        }
    }
    return false;
}

int main() {
    char grid[ROWS][COLS] = {
        {'C', 'A', 'T', 'F'},
        {'B', 'G', 'E', 'S'},
        {'I', 'T', 'A', 'E'}
    };
    const char *word = "CAT";
    if (exist(grid, word)) {
        printf("Word found\n");
    } else {
        printf("Word not found\n");
    }
    return 0;
}

A Runtime error

B Word not found

C Compilation error

D Word found

💡 Hint

Check if the word "CAT" can be traced by moving up, down, left, or right in the grid.

The word "CAT" can be found starting at grid[0][0] = 'C', then grid[0][1] = 'A', and grid[0][2] = 'T'. The backtracking search confirms this path.

❓ Predict Output

intermediate

Output of Word Search for Non-Existing Word

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

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define ROWS 3
#define COLS 4

bool dfs(char grid[ROWS][COLS], int r, int c, const char *word, int index, bool visited[ROWS][COLS]) {
    if (index == strlen(word)) return true;
    if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
    if (visited[r][c] || grid[r][c] != word[index]) return false;

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

bool exist(char grid[ROWS][COLS], const char *word) {
    bool visited[ROWS][COLS] = {false};
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (dfs(grid, i, j, word, 0, visited)) return true;
        }
    }
    return false;
}

int main() {
    char grid[ROWS][COLS] = {
        {'C', 'A', 'T', 'F'},
        {'B', 'G', 'E', 'S'},
        {'I', 'T', 'A', 'E'}
    };
    const char *word = "DOG";
    if (exist(grid, word)) {
        printf("Word found\n");
    } else {
        printf("Word not found\n");
    }
    return 0;
}

A Word not found

B Word found

C Compilation error

D Runtime error

💡 Hint

Check if the word "DOG" can be formed by adjacent letters in the grid.

The word "DOG" cannot be formed by adjacent letters in the grid, so the code prints "Word not found".

🔧 Debug

advanced

Identify the Bug in Word Search Backtracking

The following C code is intended to find if a word exists in a grid using backtracking. However, it sometimes returns incorrect results. What is the bug?

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define ROWS 2
#define COLS 2

bool dfs(char grid[ROWS][COLS], int r, int c, const char *word, int index, bool visited[ROWS][COLS]) {
    if (index == strlen(word)) return true;
    if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
    if (visited[r][c] || grid[r][c] != word[index]) return false;

    visited[r][c] = true;
    bool found = dfs(grid, r+1, c, word, index+1, visited) ||
                 dfs(grid, r-1, c, word, index+1, visited) ||
                 dfs(grid, r, c+1, word, index+1, visited) ||
                 dfs(grid, r, c-1, word, index+1, visited);
    // Missing backtracking step here
    return found;
}

bool exist(char grid[ROWS][COLS], const char *word) {
    bool visited[ROWS][COLS] = {false};
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (dfs(grid, i, j, word, 0, visited)) return true;
        }
    }
    return false;
}

int main() {
    char grid[ROWS][COLS] = {
        {'A', 'B'},
        {'C', 'D'}
    };
    const char *word = "ABCD";
    if (exist(grid, word)) {
        printf("Word found\n");
    } else {
        printf("Word not found\n");
    }
    return 0;
}

A The code uses strlen(word) inside dfs which is inefficient and causes wrong results.

B The grid size is too small to find the word, so the code always returns false.

C The code does not reset visited[r][c] to false after recursive calls, causing incorrect backtracking.

D The code does not check diagonal neighbors, so it misses some valid paths.

💡 Hint

Backtracking requires undoing the visited mark after exploring neighbors.

The bug is that visited[r][c] is never reset to false after recursive calls, so once a cell is marked visited, it stays visited for all other paths, blocking valid searches.

🧠 Conceptual

advanced

Why Use Backtracking for Word Search?

Why is backtracking the preferred method to solve the word search problem in a grid?

A Because it sorts the grid letters first to speed up the search for the word.

B Because it tries all possible paths and undoes choices when they don't lead to a solution, ensuring all options are explored.

C Because it uses dynamic programming to store intermediate results and avoid repeated work.

D Because it converts the grid into a graph and uses breadth-first search to find the word.

💡 Hint

Think about how the algorithm explores paths and handles dead ends.

Backtracking tries each possible path for the word and backtracks (undoes) when a path fails, allowing exploration of all valid paths without missing any.

❓ Predict Output

expert

Output of Word Search with Repeated Letters

What is the output of the following C code that searches for the word "ABA" in the grid using backtracking?

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define ROWS 2
#define COLS 3

bool dfs(char grid[ROWS][COLS], int r, int c, const char *word, int index, bool visited[ROWS][COLS]) {
    if (index == strlen(word)) return true;
    if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
    if (visited[r][c] || grid[r][c] != word[index]) return false;

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

bool exist(char grid[ROWS][COLS], const char *word) {
    bool visited[ROWS][COLS] = {false};
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (dfs(grid, i, j, word, 0, visited)) return true;
        }
    }
    return false;
}

int main() {
    char grid[ROWS][COLS] = {
        {'A', 'B', 'A'},
        {'B', 'A', 'B'}
    };
    const char *word = "ABA";
    if (exist(grid, word)) {
        printf("Word found\n");
    } else {
        printf("Word not found\n");
    }
    return 0;
}

A Word found

B Word not found

C Compilation error

D Runtime error

💡 Hint

Check if the word "ABA" can be formed by adjacent letters without revisiting the same cell twice.

The word "ABA" can be found multiple ways in the grid, for example starting at grid[0][0] = 'A', then grid[0][1] = 'B', then grid[0][2] = 'A'. The backtracking search confirms this.