Word Search in Grid Using Backtracking in DSA C - Build from Scratch

Word Search in Grid Using Backtracking

📖 Scenario: You are building a simple word search puzzle solver. The puzzle is a grid of letters, and you want to find if a given word exists in the grid by moving horizontally or vertically to adjacent letters.This is like searching for a hidden word in a crossword puzzle.

🎯 Goal: Build a program that checks if a given word can be found in the letter grid by moving up, down, left, or right, using backtracking to explore possible paths.

📋 What You'll Learn

Create a 2D character array representing the letter grid

Create a string variable for the word to search

Implement a backtracking function to search the word in the grid

Print whether the word exists in the grid or not

💡 Why This Matters

🌍 Real World

Word search puzzles and games use similar backtracking techniques to find words hidden in grids.

💼 Career

Backtracking algorithms are important in solving puzzles, pathfinding problems, and constraint satisfaction tasks in software development.

1

Create the letter grid

Create a 2D character array called board with 3 rows and 4 columns containing these exact letters: { {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'} }.

DSA C

# Create the 2D array board with the given letters
# Your code here

Hint

Use a 2D array of characters with 3 rows and 4 columns.

2

Create the word to search

Create a character array called word and initialize it with the string "ABCCED".

DSA C

#include 

char board[3][4] = {
    {'A', 'B', 'C', 'E'},
    {'S', 'F', 'C', 'S'},
    {'A', 'D', 'E', 'E'}
};

int main() {
    // Create the word to search
    // Your code here
    return 0;
}

Hint

Use a character array initialized with the exact string "ABCCED".

3

Implement the backtracking search function

Write a function called exist that takes the board, its row count rows, column count cols, and the word string, and returns 1 if the word exists in the board or 0 otherwise. Use backtracking to explore neighbors (up, down, left, right). Also write a helper function dfs to perform the depth-first search with parameters: board, rows, cols, current position r, c, word, and current index index. Mark visited cells temporarily by changing their value to '#' during search and restore after backtracking.

DSA C

#include 

char board[3][4] = {
    {'A', 'B', 'C', 'E'},
    {'S', 'F', 'C', 'S'},
    {'A', 'D', 'E', 'E'}
};

int dfs(char board[3][4], int rows, int cols, int r, int c, char *word, int index);
int exist(char board[3][4], int rows, int cols, char *word);

int main() {
    char word[] = "ABCCED";
    // Your code here
    return 0;
}

Hint

Use recursion to explore neighbors and mark visited cells with '#' temporarily.

4

Print if the word exists in the grid

In the main function, call exist(board, 3, 4, word) and print "Word found" if it returns 1, otherwise print "Word not found".

DSA C

#include 

char board[3][4] = {
    {'A', 'B', 'C', 'E'},
    {'S', 'F', 'C', 'S'},
    {'A', 'D', 'E', 'E'}
};

int dfs(char board[3][4], int rows, int cols, int r, int c, char *word, int index);
int exist(char board[3][4], int rows, int cols, char *word);

int main() {
    char word[] = "ABCCED";
    // Call exist and print result
    // Your code here
    return 0;
}

Hint

Use printf to print "Word found" if exist returns 1, else print "Word not found".

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