Word found following path:
(0,0)A -> (0,1)B -> (0,2)C -> (1,2)C -> (2,2)E -> (2,1)D
Annotated Code
DSA C
#include <stdio.h>#include <stdbool.h>#include <string.h>#define ROWS 3#define COLS 4bool backtrack(char board[ROWS][COLS], int row, int col, const char *word, int index, bool visited[ROWS][COLS]) {
if (index == strlen(word)) {
return true; // All letters matched
}
if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
return false; // Out of bounds
}
if (visited[row][col]) {
return false; // Already used this cell
}
if (board[row][col] != word[index]) {
return false; // Letter does not match
}
visited[row][col] = true; // Mark cell as used
// Explore neighbors: up, down, left, right
bool found = backtrack(board, row - 1, col, word, index + 1, visited) ||
backtrack(board, row + 1, col, word, index + 1, visited) ||
backtrack(board, row, col - 1, word, index + 1, visited) ||
backtrack(board, row, col + 1, word, index + 1, visited);
if (!found) {
visited[row][col] = false; // Backtrack
}
return found;
}
bool exist(char board[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 (backtrack(board, i, j, word, 0, visited)) {
return true;
}
}
}
return false;
}
int main() {
char board[ROWS][COLS] = {
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
const char *word = "ABCCED";
if (exist(board, word)) {
printf("Word '%s' found in the grid.\n", word);
} else {
printf("Word '%s' NOT found in the grid.\n", word);
}
return0;
}
if (index == strlen(word)) { return true; }
Check if all letters matched, success condition
if (row < 0 || row >= ROWS || col < 0 || col >= COLS) { return false; }
Stop if out of grid bounds
if (visited[row][col]) { return false; }
Avoid revisiting same cell in current path
if (board[row][col] != word[index]) { return false; }
Current cell letter must match current word letter
visited[row][col] = true;
Mark current cell as used
bool found = backtrack(...) || backtrack(...) || backtrack(...) || backtrack(...);
Try all four directions recursively
if (!found) { visited[row][col] = false; }
Backtrack if no path found from here
for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { if (backtrack(...)) return true; } }
Try starting from every cell in the grid
OutputSuccess
Word 'ABCCED' found in the grid.
Complexity Analysis
Time: O(N * 3^L) where N is total cells and L is word length, because from each cell we explore up to 3 directions recursively for each letter
Space: O(L) for recursion stack and visited tracking proportional to word length
vs Alternative: Naive search checking all paths without pruning would be much slower; backtracking prunes invalid paths early
Edge Cases
Empty word
Returns true immediately since empty word is trivially found
DSA C
if (index == strlen(word)) { return true; }
Word longer than total cells
Returns false quickly as no path can cover more letters than cells
DSA C
Implicitly handled by recursion depth and visited checks
Word with repeated letters requiring revisiting cells
Does not reuse cells in same path due to visited array, preventing invalid matches
DSA C
if (visited[row][col]) { return false; }
When to Use This Pattern
When asked to find a path or sequence in a grid with constraints on movement and no reuse of cells, use backtracking to explore all valid paths efficiently.
Common Mistakes
Mistake: Not marking cells as visited before recursive calls, causing infinite loops or revisiting Fix: Mark visited before recursion and unmark after if path fails (backtracking)
Mistake: Checking out-of-bounds after accessing board cell, causing errors Fix: Check boundaries before accessing board cells
Summary
Finds if a word exists in a grid by moving stepwise in four directions without reusing cells.
Use when searching for sequences in grids with adjacency and no cell reuse constraints.
The key is to try all paths and backtrack when a path does not lead to a solution.