Blog 6: Word Search & Grid-Based Backtracking🧩

Backtracking really shines when problems involve navigating a 2D grid, making decisions at each step, and exploring multiple paths.
One of the most common categories here: Word Search and related grid exploration puzzles.

---

🔹 Problem Definition: Word Search (LeetCode 79)

Given an m x n grid of characters and a word, check if the word exists in the grid.

• The word can be constructed from letters of sequentially adjacent cells (up, down, left, right).
• The same letter cell cannot be used more than once.

📌 Example:

Board =
A B C E
S F C S
A D E E

Word = "ABCCED" → true
Word = "SEE" → true
Word = "ABCB" → false

---

🔹 Intuition

• Start from every cell that matches the first letter.
• From each cell, try moving in 4 directions.
• Mark visited cells to avoid reuse.
• If we reach the last character → success.
• If all paths fail → word not found.

👉 This is a DFS with backtracking problem.

---

🔹 Java Implementation

public class WordSearch {
    private int rows, cols;
    private char[][] board;
    private String word;

    public boolean exist(char[][] board, String word) {
        this.rows = board.length;
        this.cols = board[0].length;
        this.board = board;
        this.word = word;

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

    private boolean dfs(int r, int c, int index) {
        if (index == word.length()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word.charAt(index)) 
            return false;

        char temp = board[r][c];
        board[r][c] = '#'; // mark visited

        boolean found = dfs(r + 1, c, index + 1) ||
                        dfs(r - 1, c, index + 1) ||
                        dfs(r, c + 1, index + 1) ||
                        dfs(r, c - 1, index + 1);

        board[r][c] = temp; // backtrack
        return found;
    }
}

---

🔹 Dry Run Example

Word = "ABCCED"

• Start from A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1) → ✅ success.
• Backtracking ensures we explore all possibilities without revisiting cells.

---

🔹 Complexity Analysis

• Time: O(M * N * 4^L)

  • M, N = grid size, L = word length.
  • Each step can branch into 4 directions.

• Space: O(L) recursion depth + visited cells marking.

---

🔹 Variations of Grid-Based Backtracking

1. Word Search II (LeetCode 212)

• Instead of a single word, find multiple words from a dictionary.
• Use a Trie + Backtracking to prune searches efficiently.

class WordSearchII {
    private Set<String> result = new HashSet<>();
    private boolean[][] visited;
    private int rows, cols;

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        rows = board.length;
        cols = board[0].length;
        visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j, root, "");
            }
        }
        return new ArrayList<>(result);
    }

    private void dfs(char[][] board, int r, int c, TrieNode node, String path) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c]) return;

        char ch = board[r][c];
        if (!node.children.containsKey(ch)) return;

        visited[r][c] = true;
        node = node.children.get(ch);
        String newPath = path + ch;

        if (node.isWord) result.add(newPath);

        dfs(board, r + 1, c, node, newPath);
        dfs(board, r - 1, c, node, newPath);
        dfs(board, r, c + 1, node, newPath);
        dfs(board, r, c - 1, node, newPath);

        visited[r][c] = false;
    }

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.isWord = true;
        }
        return root;
    }

    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isWord = false;
    }
}

---

2. Rat in a Maze

• Start at top-left, reach bottom-right.
• Only move down or right.
• Classic recursion + backtracking problem.

---

3. Knight’s Tour (Chessboard)

• Place knight at starting cell, visit all cells exactly once.
• Backtracking + heuristics (Warnsdorff’s rule).

---

4. Sudoku Solver (LeetCode 37)

• Fill a 9x9 board with digits 1–9 such that each row, column, and subgrid is valid.
• Try filling empty cells → recurse → backtrack on failure.

---

🔹 Key Takeaways

✅ Grid-based backtracking problems are DFS search problems.
✅ Mark visited cells → recurse → backtrack to restore state.
✅ Use Trie for multi-word optimizations (Word Search II).
✅ Advanced problems: Sudoku Solver, Knight’s Tour, Rat in a Maze.

---