Puzzles and Word Search

Backtracking: Puzzles and Word Search

The Maze Runner’s Secret 🏃‍♂️

Imagine you’re in a giant maze. You take a path, hit a wall, then walk back and try another path. That’s backtracking!

It’s like being a detective who:

1. Makes a guess
2. Checks if it works
3. If not, undoes the guess and tries something else

Simple Rule: Try → Check → Wrong? Go back and try again!

🎯 The Five Puzzles We’ll Solve

1. N-Queens Problem 👑

The Story

You have a chessboard and N queens. Queens can attack in all directions - up, down, left, right, and diagonals.

Your Mission: Place all N queens so none can attack each other.

graph TD
    A["Start with empty board"] --> B["Try placing queen in row 1"]
    B --> C{Is it safe?}
    C -->|Yes| D["Move to next row"]
    C -->|No| E["Try next column"]
    D --> F{All queens placed?}
    F -->|Yes| G["Solution Found!"]
    F -->|No| B
    E --> H{No more columns?}
    H -->|Yes| I["Backtrack to previous row"]
    I --> B

Think Like a 5-Year-Old

Imagine placing toys on a grid. Each toy says “I don’t want to see any other toy!”

• They can’t be in the same row ❌
• They can’t be in the same column ❌
• They can’t see each other diagonally ❌

The Code Pattern

void solveNQueens(int row, int n,
                  int[] board) {
    // Base case: all queens placed
    if (row == n) {
        printSolution(board);
        return;
    }

    // Try each column
    for (int col = 0; col < n; col++) {
        if (isSafe(row, col, board)) {
            board[row] = col;  // Place
            solveNQueens(row+1, n, board);
            // Backtrack happens
            // automatically!
        }
    }
}

The Safety Check

boolean isSafe(int row, int col,
               int[] board) {
    for (int i = 0; i < row; i++) {
        // Same column?
        if (board[i] == col)
            return false;
        // Same diagonal?
        if (Math.abs(board[i] - col)
            == Math.abs(i - row))
            return false;
    }
    return true;
}

Visual Example (4-Queens)

Solution 1:    Solution 2:
. Q . .        . . Q .
. . . Q        Q . . .
Q . . .        . . . Q
. . Q .        . Q . .

💡 Key Insight: For N=4, there are only 2 solutions!

2. Sudoku Solver 🔢

The Story

A 9x9 grid with some numbers filled. Your job: fill the rest!

Rules (Super Simple):

• Each row has 1-9 (no repeats)
• Each column has 1-9 (no repeats)
• Each 3x3 box has 1-9 (no repeats)

Think Like a 5-Year-Old

You have 9 crayons numbered 1-9. In each row, column, and small box, you must use each crayon exactly once!

graph TD
    A["Find empty cell"] --> B{Cell found?}
    B -->|No| C["Puzzle Solved!"]
    B -->|Yes| D["Try numbers 1-9"]
    D --> E{Number valid?}
    E -->|Yes| F["Place number"]
    F --> A
    E -->|No| G["Try next number"]
    G --> H{All numbers tried?}
    H -->|Yes| I["Backtrack!"]
    H -->|No| D
    I --> J["Remove number"]
    J --> D

The Code Pattern

boolean solveSudoku(int[][] board) {
    // Find empty cell
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == 0) {
                // Try 1-9
                for (int num = 1;
                     num <= 9; num++) {
                    if (isValid(board,
                        row, col, num)) {
                        board[row][col] = num;

                        if (solveSudoku(board))
                            return true;

                        // Backtrack!
                        board[row][col] = 0;
                    }
                }
                return false; // No valid num
            }
        }
    }
    return true; // All filled!
}

The Validation Check

boolean isValid(int[][] board,
    int row, int col, int num) {
    // Check row
    for (int i = 0; i < 9; i++)
        if (board[row][i] == num)
            return false;

    // Check column
    for (int i = 0; i < 9; i++)
        if (board[i][col] == num)
            return false;

    // Check 3x3 box
    int boxRow = row - row % 3;
    int boxCol = col - col % 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (board[boxRow+i][boxCol+j]
                == num) return false;

    return true;
}

💡 Pro Tip: The 3x3 box check uses row - row % 3 to find the box’s top-left corner!

3. Word Search in Grid 🔍

The Story

You have a grid of letters. Can you find a hidden word by moving up, down, left, or right?

Think Like a 5-Year-Old

It’s like finding your name in a word-search puzzle! Start at any letter, then walk step-by-step to spell the word.

Example

Grid:          Find: "CAT"
A B C E
S F C S        Path: C(0,2) → A(0,0)? No!
A D E E        Path: C(1,2) → A? No neighbor A!
               Keep trying...

The Code Pattern

boolean exist(char[][] board,
              String word) {
    for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[0].length; j++)
            if (search(board, word, i, j, 0))
                return true;
    return false;
}

boolean search(char[][] board, String word,
    int i, int j, int index) {
    // Word complete!
    if (index == word.length())
        return true;

    // Out of bounds or wrong letter
    if (i < 0 || j < 0 ||
        i >= board.length ||
        j >= board[0].length ||
        board[i][j] != word.charAt(index))
        return false;

    // Mark as visited
    char temp = board[i][j];
    board[i][j] = '#';

    // Try all 4 directions
    boolean found =
        search(board, word, i+1, j, index+1) ||
        search(board, word, i-1, j, index+1) ||
        search(board, word, i, j+1, index+1) ||
        search(board, word, i, j-1, index+1);

    // Backtrack - restore cell
    board[i][j] = temp;
    return found;
}

💡 Key Trick: We mark visited cells with ‘#’ to avoid using the same letter twice!

4. Word Search II 🔍🔍

The Story

Same grid, but now find multiple words at once! Using a Trie makes this super fast.

Why Trie?

Without Trie: Search each word separately → SLOW With Trie: Search all words together → FAST!

graph TD
    A["Build Trie with all words"] --> B["Start DFS from each cell"]
    B --> C["Match letters with Trie nodes"]
    C --> D{Word found?}
    D -->|Yes| E["Add to results"]
    D -->|No| F["Continue search"]
    E --> F
    F --> G{More paths?}
    G -->|Yes| C
    G -->|No| H["Backtrack"]

The Trie Structure

class TrieNode {
    TrieNode[] children =
        new TrieNode[26];
    String word = null; // Store word here!
}

The Code Pattern

List<String> findWords(char[][] board,
                       String[] words) {
    List<String> result = new ArrayList<>();
    TrieNode root = buildTrie(words);

    for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[0].length; j++)
            dfs(board, i, j, root, result);

    return result;
}

void dfs(char[][] board, int i, int j,
         TrieNode node, List<String> result) {
    char c = board[i][j];
    if (c == '#' ||
        node.children[c-'a'] == null) return;

    node = node.children[c - 'a'];
    if (node.word != null) {
        result.add(node.word);
        node.word = null; // Avoid duplicates
    }

    board[i][j] = '#'; // Mark visited

    // Explore 4 directions
    if (i > 0) dfs(board, i-1, j, node, result);
    if (j > 0) dfs(board, i, j-1, node, result);
    if (i < board.length-1)
        dfs(board, i+1, j, node, result);
    if (j < board[0].length-1)
        dfs(board, i, j+1, node, result);

    board[i][j] = c; // Backtrack
}

💡 Super Power: Trie lets us search multiple words in ONE pass through the grid!

5. Letter Combinations of Phone Number 📱

The Story

Old phones had letters on number buttons:

• 2 → ABC
• 3 → DEF
• 4 → GHI
• … and so on

Given digits like “23”, find ALL possible letter combinations!

Think Like a 5-Year-Old

Button 2 has A, B, C. Button 3 has D, E, F.

For “23”, you pick one letter from 2, one from 3:

• A+D, A+E, A+F
• B+D, B+E, B+F
• C+D, C+E, C+F

That’s 9 combinations!

The Code Pattern

String[] mapping = {
    "", "", "abc", "def", "ghi",
    "jkl", "mno", "pqrs", "tuv", "wxyz"
};

List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits.isEmpty()) return result;

    backtrack(digits, 0, new StringBuilder(),
              result);
    return result;
}

void backtrack(String digits, int index,
    StringBuilder current, List<String> result) {
    // Built full combination
    if (index == digits.length()) {
        result.add(current.toString());
        return;
    }

    // Get letters for current digit
    String letters = mapping[
        digits.charAt(index) - '0'];

    for (char letter : letters.toCharArray()) {
        current.append(letter);      // Choose
        backtrack(digits, index + 1,
                  current, result);  // Explore
        current.deleteCharAt(
            current.length() - 1);   // Backtrack
    }
}

Visual Example

Input: "23"

        Start
       /  |  \
      A   B   C     (from '2')
     /|\  /|\  /|\
    D E F D E F D E F  (from '3')

Output: [ad, ae, af, bd, be, bf, cd, ce, cf]

💡 Pattern: For N digits, you get up to 4^N combinations (since some buttons have 4 letters)!

The Backtracking Template 📋

Every backtracking problem follows this pattern:

void backtrack(state, choices) {
    // 1. Base case: solution found?
    if (isSolution(state)) {
        saveSolution(state);
        return;
    }

    // 2. Try each choice
    for (choice in choices) {
        if (isValid(choice)) {
            // 3. Make choice
            makeChoice(state, choice);

            // 4. Recurse
            backtrack(newState, newChoices);

            // 5. Undo choice (backtrack!)
            undoChoice(state, choice);
        }
    }
}

Summary: The 5 Puzzles at a Glance

You Did It! 🎉

You now understand backtracking! Remember:

1. Try a choice
2. Check if it works
3. Backtrack if it doesn’t
4. Repeat until solved

Think of it as a polite guest who always cleans up before leaving! 🧹

Final Wisdom: Backtracking is slow but correct. When you need to find ALL solutions or prove none exist, backtracking is your friend!