Puzzles and Word Search

🧩 Backtracking: Puzzles & Word Search

The Treasure Hunter’s Quest

Imagine you’re a treasure hunter in a magical maze. You walk down a path, and when you hit a dead end, you go back to the last crossroad and try a different path. You keep doing this until you find the treasure!

That’s backtracking! Try something, and if it doesn’t work, undo it and try something else.

🔑 The Magic Rule

1. Make a choice
2. Check if it works
3. If stuck → go back (backtrack)
4. Try a different choice
5. Repeat until solved!

Think of it like trying keys on a lock. If one key doesn’t fit, you put it back and try the next one.

👑 The N-Queens Problem

The Story

Once upon a time, there were N queens who wanted to live on a chessboard. But queens are very picky! No queen wants to share her row, column, or diagonal with another queen. Can you place all N queens safely?

Why Queens Fight

On a chessboard, a queen can attack:

• ↔️ Same row (left and right)
• ↕️ Same column (up and down)
• ↗️↙️ Same diagonals (corners)

How We Solve It

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 rows done?}
    F -->|Yes| G["🎉 Solution found!"]
    F -->|No| B
    E --> H{More columns?}
    H -->|No| I["Backtrack to previous row"]
    I --> E
    H -->|Yes| C

JavaScript Example

function solveNQueens(n) {
  const board = [];
  const result = [];

  function isSafe(row, col) {
    // Check column above
    for (let i = 0; i < row; i++) {
      if (board[i] === col) return false;
      // Check diagonals
      if (Math.abs(board[i] - col) ===
          Math.abs(i - row)) return false;
    }
    return true;
  }

  function solve(row) {
    if (row === n) {
      result.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row] = col;  // Place queen
        solve(row + 1);    // Try next row
        // Backtrack happens automatically
      }
    }
  }

  solve(0);
  return result;
}

4-Queens Solution Visual

. Q . .    Q = Queen
. . . Q    . = Empty
Q . . .
. . Q .

Each queen is alone in her row, column, and diagonals!

🔢 Sudoku Solver

The Story

Sudoku is like a number puzzle party! You have a 9×9 grid, and each row, column, and 3×3 box must have numbers 1-9. No repeats allowed at the party!

The Rules (Like Party Rules)

How We Solve It

graph TD
    A["Find empty cell"] --> B{Any empty?}
    B -->|No| C["🎉 Solved!"]
    B -->|Yes| D["Try number 1-9"]
    D --> E{Is it valid?}
    E -->|Yes| F["Place number"]
    F --> A
    E -->|No| G["Try next number"]
    G --> H{Tried all 9?}
    H -->|Yes| I["Backtrack - remove number"]
    I --> G
    H -->|No| E

JavaScript Example

function solveSudoku(board) {
  function isValid(board, row, col, num) {
    // Check row
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === num) return false;
    }
    // Check column
    for (let i = 0; i < 9; i++) {
      if (board[i][col] === num) return false;
    }
    // Check 3x3 box
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[boxRow + i][boxCol + j] === num)
          return false;
      }
    }
    return true;
  }

  function solve() {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (board[row][col] === '.') {
          for (let num = 1; num <= 9; num++) {
            const char = String(num);
            if (isValid(board, row, col, char)) {
              board[row][col] = char;
              if (solve()) return true;
              board[row][col] = '.'; // Backtrack!
            }
          }
          return false; // No number works
        }
      }
    }
    return true; // All filled!
  }

  solve();
  return board;
}

Think About It

When you try a number and it leads to a dead end, you erase it (backtrack) and try the next number. Just like erasing a wrong answer on a test!

🔍 Word Search in Grid

The Story

Imagine you have a box of letter tiles. Can you find a hidden word by walking through connected letters? You can walk up, down, left, or right, but you can’t reuse the same tile!

The Grid

B O A R D
A B C D E
L E A R N
L O O P S

Can you find “BOARD”? Start at B, go right through O-A-R-D!

How We Solve It

graph TD
    A["Start at each cell"] --> B{First letter match?}
    B -->|No| C["Try next cell"]
    B -->|Yes| D["Mark as visited"]
    D --> E["Check 4 neighbors"]
    E --> F{Next letter found?}
    F -->|Yes| G["Move there recursively"]
    F -->|No| H["Backtrack - unmark cell"]
    G --> I{Word complete?}
    I -->|Yes| J["🎉 Found!"]
    I -->|No| E
    H --> C

JavaScript Example

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;

  function search(row, col, index) {
    // Word complete!
    if (index === word.length) return true;

    // Out of bounds or wrong letter
    if (row < 0 || row >= rows ||
        col < 0 || col >= cols ||
        board[row][col] !== word[index]) {
      return false;
    }

    // Mark as visited
    const temp = board[row][col];
    board[row][col] = '#';

    // Try all 4 directions
    const found = search(row + 1, col, index + 1) ||
                  search(row - 1, col, index + 1) ||
                  search(row, col + 1, index + 1) ||
                  search(row, col - 1, index + 1);

    // Backtrack - restore cell
    board[row][col] = temp;

    return found;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (search(r, c, 0)) return true;
    }
  }
  return false;
}

Key Insight

We mark cells as visited with # so we don’t walk in circles. When we backtrack, we restore the original letter!

🔍🔍 Word Search II (Multiple Words)

The Story

Now imagine you have a list of words to find in the same grid. Searching one by one would be slow. Let’s be smart and use a Trie (a word tree)!

What’s a Trie?

Think of a Trie like a family tree, but for letters:

        root
       / | \
      B  C  L
      |     |
      A     E
      |     |
      L     A
      |     |
      L     R
            |
            N

This Trie holds “BALL” and “LEARN”!

The Smart Strategy

1. Build a Trie from all words
2. Search the grid once
3. At each cell, check if path exists in Trie
4. Collect all found words!

JavaScript Example

function findWords(board, words) {
  const result = [];
  const trie = {};

  // Build Trie
  for (const word of words) {
    let node = trie;
    for (const char of word) {
      if (!node[char]) node[char] = {};
      node = node[char];
    }
    node.word = word; // Mark end of word
  }

  function search(row, col, node) {
    if (row < 0 || row >= board.length ||
        col < 0 || col >= board[0].length)
      return;

    const char = board[row][col];
    if (!node[char]) return;

    node = node[char];
    if (node.word) {
      result.push(node.word);
      node.word = null; // Avoid duplicates
    }

    board[row][col] = '#'; // Mark visited

    search(row + 1, col, node);
    search(row - 1, col, node);
    search(row, col + 1, node);
    search(row, col - 1, node);

    board[row][col] = char; // Backtrack
  }

  for (let r = 0; r < board.length; r++) {
    for (let c = 0; c < board[0].length; c++) {
      search(r, c, trie);
    }
  }
  return result;
}

Why Trie is Magic

Without Trie: Search each word separately = SLOW With Trie: One search finds ALL words = FAST!

📱 Letter Combinations of Phone Number

The Story

Remember old phone keypads? Each number had letters:

If you press “23”, what words can you spell?

All Combinations for “23”

2 → A, B, C
3 → D, E, F

Combinations:
AD, AE, AF, BD, BE, BF, CD, CE, CF

How We Solve It

graph TD
    A["Start with digits"] --> B["Pick first digit"]
    B --> C["Try each letter"]
    C --> D{More digits?}
    D -->|Yes| E["Pick next digit"]
    E --> C
    D -->|No| F["Save combination"]
    F --> G["Backtrack"]
    G --> C

JavaScript Example

function letterCombinations(digits) {
  if (!digits.length) return [];

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

  const result = [];

  function backtrack(index, current) {
    // Built complete combination
    if (index === digits.length) {
      result.push(current);
      return;
    }

    // Get letters for current digit
    const letters = phone[digits[index]];

    // Try each letter
    for (const letter of letters) {
      backtrack(index + 1, current + letter);
      // Backtrack is automatic (we pass new string)
    }
  }

  backtrack(0, '');
  return result;
}

// Example
letterCombinations("23");
// Returns: ["ad","ae","af","bd","be","bf",
//           "cd","ce","cf"]

Think About It

Each digit gives us choices. We pick one letter, move to the next digit, pick another, and so on. When done, we’ve built one combination!

🎯 The Backtracking Pattern

Every backtracking problem follows this recipe:

function backtrack(state) {
  // 1. Base case - are we done?
  if (isComplete(state)) {
    saveSolution(state);
    return;
  }

  // 2. Try all choices
  for (const choice of getChoices(state)) {
    // 3. Make the choice
    makeChoice(state, choice);

    // 4. Recurse
    backtrack(state);

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

Remember

🌟 You Made It!

Backtracking is like being a detective who:

1. Tries a path
2. Checks if it works
3. Goes back if stuck
4. Tries again until successful

Now go solve some puzzles! 🧩