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".