🔙 PHP Backtracking

Parent: Recursion & Backtracking Index

---

What is Backtracking?

Backtracking = Recursion + Undo. You explore a decision tree, and when a path fails, you undo the last choice and try a different option.

Think of it like solving a maze:
→ Move forward
→ Hit a wall? Go back (backtrack)
→ Try a different direction
→ Repeat until you reach the exit

The Universal Template

function backtrack(array &$result, array &$current, /* state */): void
{
    // 1. BASE CASE: found a valid complete solution
    if (isComplete()) {
        $result[] = $current;  // save it
        return;
    }

    // 2. Try every available choice
    foreach (getChoices() as $choice) {
        if (!isValid($choice)) continue; // prune invalid

        // 3. CHOOSE
        $current[] = $choice;
        markUsed($choice);

        // 4. EXPLORE
        backtrack($result, $current, /* updated state */);

        // 5. UN-CHOOSE (backtrack)
        array_pop($current);
        markUnused($choice);
    }
}

---

Q1. N-Queens Problem

Problem: Place N queens on an N×N chessboard so no two queens threaten each other (no same row, column, or diagonal).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Place one queen per row. For each column in that row, check if safe → place → recurse to next row → backtrack.

Step 2 — Safety check:

Queens threaten same column, or diagonals where |row1-row2| == |col1-col2|.

Step 3 — Algorithm:

1. For each row, try placing queen in each column

2. Check: no other queen in same col, no queen on same diagonal

3. If safe: place queen (mark column), recurse to next row, remove queen

4. Base case: row == n → found a valid placement

Step 4 — Edge cases:

- n=1: one solution [[Q]]

- n=2, n=3: no solutions

function solveNQueens(int $n): array
{
    $result = [];
    $board  = array_fill(0, $n, array_fill(0, $n, '.'));

    function isSafe(array $board, int $row, int $col, int $n): bool
    {
        // Check column above
        for ($i = 0; $i < $row; $i++) {
            if ($board[$i][$col] === 'Q') return false;
        }
        // Check upper-left diagonal
        for ($i = $row - 1, $j = $col - 1; $i >= 0 && $j >= 0; $i--, $j--) {
            if ($board[$i][$j] === 'Q') return false;
        }
        // Check upper-right diagonal
        for ($i = $row - 1, $j = $col + 1; $i >= 0 && $j < $n; $i--, $j++) {
            if ($board[$i][$j] === 'Q') return false;
        }
        return true;
    }

    function solve(array &$board, int $row, int $n, array &$result): void
    {
        // Base case: all queens placed
        if ($row === $n) {
            $result[] = array_map('implode', $board); // convert rows to strings
            return;
        }

        for ($col = 0; $col < $n; $col++) {
            if (isSafe($board, $row, $col, $n)) {
                // CHOOSE
                $board[$row][$col] = 'Q';

                // EXPLORE
                solve($board, $row + 1, $n, $result);

                // UN-CHOOSE
                $board[$row][$col] = '.';
            }
        }
    }

    solve($board, 0, $n, $result);
    return $result;
}

$solutions = solveNQueens(4);
echo count($solutions); // 2
foreach ($solutions[0] as $row) echo $row . "\n";
// .Q..
// ...Q
// Q...
// ..Q.

Time: O(n!) | Space: O(n²) for board

---

Q2. Sudoku Solver

Problem: Solve a 9×9 Sudoku puzzle. Fill in empty cells (marked '.') with digits 1-9, each digit appears once per row, column, and 3×3 box.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Fill cells one by one. For each empty cell, try 1-9, check validity, recurse → backtrack if stuck.

Step 2 — Validity check:

Digit must not exist in same row, column, or 3×3 box.

Step 3 — Algorithm:

1. Find next empty cell ('.')

2. Try digits 1-9: if valid → place → recurse → if recursion returns true → done

3. If no digit works → backtrack (restore '.')

4. Base case: no empty cell found → puzzle solved!

Step 4 — Box index:

box_row = row/3, box_col = col/3

function solveSudoku(array &$board): bool
{
    for ($row = 0; $row < 9; $row++) {
        for ($col = 0; $col < 9; $col++) {
            if ($board[$row][$col] !== '.') continue;

            // Try each digit 1-9
            for ($d = 1; $d <= 9; $d++) {
                $ch = (string)$d;
                if (isValidSudoku($board, $row, $col, $ch)) {
                    // CHOOSE
                    $board[$row][$col] = $ch;

                    // EXPLORE
                    if (solveSudoku($board)) return true;

                    // UN-CHOOSE
                    $board[$row][$col] = '.';
                }
            }
            return false; // No digit worked — backtrack
        }
    }
    return true; // All cells filled — solved!
}

function isValidSudoku(array $board, int $row, int $col, string $ch): bool
{
    for ($i = 0; $i < 9; $i++) {
        if ($board[$row][$i] === $ch) return false; // Same row
        if ($board[$i][$col] === $ch) return false; // Same col

        // Same 3x3 box
        $boxRow = 3 * intdiv($row, 3) + intdiv($i, 3);
        $boxCol = 3 * intdiv($col, 3) + ($i % 3);
        if ($board[$boxRow][$boxCol] === $ch) return false;
    }
    return true;
}

Time: O(9^81) worst case, much faster in practice | Space: O(81) = O(1)

---

Q3. Word Search in Grid

Problem: Given a 2D grid of characters and a word, return true if the word exists in the grid (horizontal/vertical, connected cells, no reuse).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

DFS + Backtracking on 2D grid. Explore 4 directions, mark visited, backtrack.

Step 2 — Algorithm:

1. For each cell in grid: if it matches word[0], start DFS

2. DFS: if index == word length → found it (return true)

3. Mark cell as visited (e.g., change to '#')

4. Try all 4 neighbors: if valid and next char matches → recurse

5. Restore cell (backtrack)

Step 3 — Edge cases:

- Out of bounds: skip

- Already visited: skip

- No match found: return false

function wordSearch(array $board, string $word): bool
{
    $rows = count($board);
    $cols = count($board[0]);

    function dfs(array &$board, int $r, int $c, string $word, int $idx): bool
    {
        // Base case: matched entire word
        if ($idx === strlen($word)) return true;

        // Boundary & mismatch check
        if ($r < 0 || $r >= count($board) ||
            $c < 0 || $c >= count($board[0]) ||
            $board[$r][$c] !== $word[$idx]) {
            return false;
        }

        // CHOOSE: mark as visited
        $temp = $board[$r][$c];
        $board[$r][$c] = '#';

        // EXPLORE all 4 directions
        $found = dfs($board, $r + 1, $c, $word, $idx + 1) ||
                 dfs($board, $r - 1, $c, $word, $idx + 1) ||
                 dfs($board, $r, $c + 1, $word, $idx + 1) ||
                 dfs($board, $r, $c - 1, $word, $idx + 1);

        // UN-CHOOSE: restore cell
        $board[$r][$c] = $temp;

        return $found;
    }

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if (dfs($board, $r, $c, $word, 0)) return true;
        }
    }
    return false;
}

$board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
];
var_dump(wordSearch($board, "ABCCED")); // true
var_dump(wordSearch($board, "SEE"));    // true
var_dump(wordSearch($board, "ABCB"));   // false

Time: O(m×n×4^L) where L=word length | Space: O(L)

---

Q4. Generate Parentheses

Problem: Generate all combinations of n pairs of valid parentheses.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

At each step, decide to add '(' or ')'. Valid constraints: open count <= n, close count <= open count.

Step 2 — Pruning rules:

- Add '(' if openCount < n

- Add ')' if closeCount < openCount

Step 3 — Algorithm:

1. Start with empty string, open=0, close=0

2. If open < n: add '(', recurse(open+1, close)

3. If close < open: add ')', recurse(open, close+1)

4. Base case: string length == 2n → add to result

function generateParentheses(int $n): array
{
    $result = [];

    function generate(string $current, int $open, int $close, int $n, array &$result): void
    {
        // Base case: complete valid string
        if (strlen($current) === 2 * $n) {
            $result[] = $current;
            return;
        }

        // Add opening parenthesis if we still can
        if ($open < $n) {
            generate($current . '(', $open + 1, $close, $n, $result);
        }

        // Add closing parenthesis if valid
        if ($close < $open) {
            generate($current . ')', $open, $close + 1, $n, $result);
        }
    }

    generate('', 0, 0, $n, $result);
    return $result;
}

$result = generateParentheses(3);
// ["((()))", "(()())", "(())()", "()(())", "()()()"]
echo count($result); // 5 (Catalan number C(3))

Time: O(4ⁿ/√n) (Catalan number) | Space: O(n)

---

Q5. Letter Combinations of a Phone Number

Problem: Given a digit string like "23", return all possible letter combinations (T9 keyboard: 2=abc, 3=def, ...).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

For each digit, branch into all its letters. Backtracking on choices per digit.

Step 2 — Algorithm:

1. Map each digit to its letters

2. For each digit's letter: add to current, recurse to next digit, remove (backtrack)

3. Base case: processed all digits → add current combination to result

function letterCombinations(string $digits): array
{
    if (empty($digits)) return [];

    $phoneMap = [
        '2' => 'abc', '3' => 'def', '4' => 'ghi',
        '5' => 'jkl', '6' => 'mno', '7' => 'pqrs',
        '8' => 'tuv', '9' => 'wxyz'
    ];

    $result  = [];
    $current = '';

    function backtrack(
        string  $digits,
        int     $index,
        string  &$current,
        array   $phoneMap,
        array   &$result
    ): void {
        // Base case: used all digits
        if ($index === strlen($digits)) {
            $result[] = $current;
            return;
        }

        $letters = $phoneMap[$digits[$index]];
        for ($i = 0; $i < strlen($letters); $i++) {
            $current .= $letters[$i];                          // CHOOSE
            backtrack($digits, $index + 1, $current, $phoneMap, $result); // EXPLORE
            $current = substr($current, 0, -1);               // UN-CHOOSE
        }
    }

    backtrack($digits, 0, $current, $phoneMap, $result);
    return $result;
}

$result = letterCombinations("23");
// ["ad","ae","af","bd","be","bf","cd","ce","cf"]
echo count($result); // 9

Time: O(4ⁿ × n) where n = digits length | Space: O(n)

---

Backtracking Summary