Puzzles and Word Search

🧩 Backtracking: Solving Puzzles Like a Detective

The Treasure Hunt Story

Imagine you’re in a big maze looking for treasure. You pick a path and walk forward. If you hit a dead end, what do you do? You go back to the last fork and try a different path!

That’s backtracking — trying a choice, and if it doesn’t work, going back and trying something else.

Think of it like this:
┌─────────────────────────────┐
│  Try something              │
│      ↓                      │
│  Does it work?              │
│      ↓                      │
│  YES → Keep going!          │
│  NO  → Go back, try again   │
└─────────────────────────────┘

🏰 The N-Queens Problem

The Story

You have a chessboard and N queens. Queens can attack in any direction — left, right, up, down, and diagonally. Your job? Place all N queens so no queen can attack another.

It’s like seating N royal guests at a party where each one needs their own space!

How It Works

def solve_queens(board, col, n):
    # Base case: all queens placed!
    if col >= n:
        return True

    # Try each row in this column
    for row in range(n):
        if is_safe(board, row, col, n):
            board[row][col] = 1  # Place queen

            # Try next column
            if solve_queens(board, col + 1, n):
                return True

            # Backtrack! Remove queen
            board[row][col] = 0

    return False

Visual Example (4 Queens)

Try column 0, row 0: ✓ Place Q
  [Q . . .]
  [. . . .]
  [. . . .]
  [. . . .]

Try column 1... row 0? ✗ (attacked)
             row 1? ✗ (attacked diagonally)
             row 2? ✓ Place Q

  [Q . . .]
  [. . . .]
  [. Q . .]
  [. . . .]

Keep going... if stuck, BACKTRACK!

The Magic Pattern

1. Choose — Pick a row for the queen
2. Check — Is it safe from attacks?
3. Continue — Move to next column
4. Backtrack — If stuck, remove queen and try another row

🔢 Sudoku Solver

The Story

Sudoku is like a number puzzle party! You have a 9×9 grid, and every row, column, and 3×3 box must have numbers 1-9 exactly once. It’s like making sure every guest at 9 tables gets exactly one slice of each flavor of cake!

How It Works

def solve_sudoku(board):
    # Find empty cell
    empty = find_empty(board)
    if not empty:
        return True  # Puzzle solved!

    row, col = empty

    # Try numbers 1-9
    for num in range(1, 10):
        if is_valid(board, num, row, col):
            board[row][col] = num

            if solve_sudoku(board):
                return True

            # Backtrack!
            board[row][col] = 0

    return False

The Rules Check

def is_valid(board, num, row, col):
    # Check row
    if num in board[row]:
        return False

    # Check column
    for r in range(9):
        if board[r][col] == num:
            return False

    # Check 3x3 box
    box_row = (row // 3) * 3
    box_col = (col // 3) * 3
    for r in range(box_row, box_row + 3):
        for c in range(box_col, box_col + 3):
            if board[r][c] == num:
                return False

    return True

Visual Walkthrough

Empty cell at [0,2]
Try 1: Row has 1? No ✓
       Col has 1? No ✓
       Box has 1? No ✓
       Place 1!

Move to next empty...
Stuck later? Come back and try 2!

🔤 Word Search in Grid

The Story

Imagine you’re playing a word hunt game. You have a grid of letters and need to find if a secret word is hiding! You can move up, down, left, or right — like a little explorer walking through letter land.

How It Works

def word_search(board, word):
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, index):
        # Found the whole word!
        if index == len(word):
            return True

        # Out of bounds or wrong letter?
        if (r < 0 or r >= rows or
            c < 0 or c >= cols or
            board[r][c] != word[index]):
            return False

        # Mark as visited
        temp = board[r][c]
        board[r][c] = '#'

        # Try all 4 directions
        found = (backtrack(r+1, c, index+1) or
                 backtrack(r-1, c, index+1) or
                 backtrack(r, c+1, index+1) or
                 backtrack(r, c-1, index+1))

        # Backtrack: restore cell
        board[r][c] = temp
        return found

    # Try starting from each cell
    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

Visual Example

Find "CAT" in:
[C][A][T][S]
[O][G][E][N]
[D][O][G][S]

Start at C[0,0] → A[0,1] → T[0,2]
Found it! ✓

🔍 Word Search II (Multiple Words)

The Story

Now you’re a super word hunter! Instead of one word, you need to find MANY words at once. The secret weapon? A Trie — a magical tree that remembers all your words!

The Trie Structure

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # Store word at end

def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word  # Mark end
    return root

The Search

def find_words(board, words):
    root = build_trie(words)
    result = []
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, node):
        char = board[r][c]

        if char not in node.children:
            return

        next_node = node.children[char]

        # Found a word!
        if next_node.word:
            result.append(next_node.word)
            next_node.word = None  # Avoid duplicates

        # Mark visited
        board[r][c] = '#'

        # Explore neighbors
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if board[nr][nc] != '#':
                    backtrack(nr, nc, next_node)

        # Backtrack
        board[r][c] = char

    for r in range(rows):
        for c in range(cols):
            backtrack(r, c, root)

    return result

Why Trie?

Without Trie: Search for each word separately
             = Slow! 😴

With Trie: Search all words at once
           = Fast! 🚀

Words: ["cat", "car", "card"]

        root
         │
         c
         │
         a
        / \
       t   r
           │
           d

📱 Letter Combinations of Phone Number

The Story

Remember old phone keypads? Each number had letters!

┌─────┬─────┬─────┐
│  1  │ 2   │ 3   │
│     │ abc │ def │
├─────┼─────┼─────┤
│ 4   │ 5   │ 6   │
│ ghi │ jkl │ mno │
├─────┼─────┼─────┤
│ 7   │ 8   │ 9   │
│pqrs │ tuv │wxyz │
└─────┴─────┴─────┘

If someone pressed “23”, what words could they be typing? Your job is to find ALL possibilities!

How It Works

def letter_combinations(digits):
    if not digits:
        return []

    phone_map = {
        '2': 'abc', '3': 'def',
        '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs',
        '8': 'tuv', '9': 'wxyz'
    }

    result = []

    def backtrack(index, path):
        # Built full combination!
        if index == len(digits):
            result.append(''.join(path))
            return

        # Get letters for current digit
        letters = phone_map[digits[index]]

        # Try each letter
        for letter in letters:
            path.append(letter)
            backtrack(index + 1, path)
            path.pop()  # Backtrack!

    backtrack(0, [])
    return result

Visual Example

Input: "23"

Digit '2' = [a, b, c]
Digit '3' = [d, e, f]

Building combinations:
  a → d → "ad" ✓
  a → e → "ae" ✓
  a → f → "af" ✓
  b → d → "bd" ✓
  ... and so on!

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

🎯 The Backtracking Recipe

Every backtracking problem follows this pattern:

┌──────────────────────────────────┐
│  1. CHOOSE: Pick an option       │
│              ↓                   │
│  2. EXPLORE: Go deeper           │
│              ↓                   │
│  3. CHECK: Is it valid?          │
│              ↓                   │
│     YES → Continue exploring     │
│     NO  → BACKTRACK (undo)       │
│              ↓                   │
│  4. REPEAT until solved!         │
└──────────────────────────────────┘

The Code Template

def backtrack(state):
    # Base case: found solution?
    if is_complete(state):
        save_solution(state)
        return

    # Try each choice
    for choice in get_choices(state):
        if is_valid(choice, state):
            make_choice(choice, state)
            backtrack(state)
            undo_choice(choice, state)  # Backtrack!

💡 Key Takeaways

Remember: Backtracking is just smart trial and error. Try something, check if it works, and if not — go back and try something else! 🚀