Backtracking on Boards

1. Introduction: Escaping the Grid

While basic backtracking focuses on linear structures (strings, 1D arrays, combinations), Board Problems escalate the complexity into 2D Matrices.

Imagine you are trying to navigate a rat through a maze to find cheese, or trying to solve a Sudoku puzzle. The core philosophy remains identical: Make a choice, recurse, undo the choice. However, instead of simply picking a number or a letter, your choices are physical movements: Up, Down, Left, Right, or placing an object (like a Chess Queen) at a specific [row][col] coordinate.

Board problems heavily test your ability to manage state. Because modifying a 2D matrix is expensive, you almost always modify the board in place, passing it down the recursion stack. You MUST meticulously clean up after yourself ("undo the choice") so you don't corrupt the board for the next recursive branch.

2. Core Concept: State Tracking and Boundaries

When backtracking on a board, you will face two main challenges:

1. Boundary Management: You must ensure your recursion doesn't step off the edge of the matrix, causing an ArrayIndexOutOfBoundsException.
2. Cycle Prevention: If you move from Cell A to Cell B, what stops you from moving back to Cell A, and getting trapped in an infinite loop?

We solve this using a boolean[][] visited matrix, or by temporarily mutating the board itself (e.g., changing a character to # while we visit it) to mark it as restricted, and changing it back when we backtrack.

3. Beginner Code Example: Rat in a Maze

Problem Statement: You have an $N \times N$ matrix. A rat starts at [0][0] and wants to reach [N-1][N-1]. The rat can only move down or right. 1 means an open path, 0 means a blocked wall. Find if a path exists.

public class RatMaze {
    
    public static boolean solveMaze(int[][] maze) {
        int n = maze.length;
        // The path board will store 1s for the successful route
        int[][] path = new int[n][n]; 
        
        if (solveMazeUtil(maze, 0, 0, path, n)) {
            printSolution(path);
            return true;
        }
        return false;
    }
    
    private static boolean solveMazeUtil(int[][] maze, int r, int c, int[][] path, int n) {
        // Base Case: Reached the destination!
        if (r == n - 1 && c == n - 1 && maze[r][c] == 1) {
            path[r][c] = 1;
            return true;
        }
        
        // Pruning: Is it safe to move here?
        if (r >= 0 && r < n && c >= 0 && c < n && maze[r][c] == 1) {
            
            path[r][c] = 1; // MAKE CHOICE: Mark as part of the solution path
            
            // Recurse Down
            if (solveMazeUtil(maze, r + 1, c, path, n)) return true;
            
            // Recurse Right
            if (solveMazeUtil(maze, r, c + 1, path, n)) return true;
            
            // UNDO CHOICE (Backtrack): This path didn't lead to the goal
            path[r][c] = 0; 
            return false;
        }
        
        return false;
    }
    
    private static void printSolution(int[][] path) {
        for (int[] row : path) {
            for (int val : row) System.out.print(val + " ");
            System.out.println();
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(2^{(N^2)})$. At every cell, the rat has 2 choices. The maximum path length is roughly $N^2$. (In reality, it's slightly faster due to pruning walls).
• Space Complexity: $O(N^2)$ for the recursion stack and the path matrix.

4. Intermediate Code Example: Word Search

Problem Statement: (LeetCode 79) Given an $M \times N$ grid of characters board and a string word, return true if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontal or vertical). The same letter cell may not be used more than once.

This introduces 4-directional movement and in-place cycle prevention.

public class WordSearch {
    public static boolean exist(char[][] board, String word) {
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                // If we find the first letter, start backtracking from here!
                if (board[r][c] == word.charAt(0) && dfs(board, r, c, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private static boolean dfs(char[][] board, int r, int c, int index, String word) {
        // Base Case: We found all characters!
        if (index == word.length()) return true;
        
        // Boundaries AND Pruning (wrong character)
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) {
            return false;
        }
        
        // MAKE CHOICE: Mark cell as visited to prevent cycles
        char temp = board[r][c];
        board[r][c] = '#'; 
        
        // RECURSE in all 4 directions
        boolean found = dfs(board, r + 1, c, index + 1, word) || // Down
                        dfs(board, r - 1, c, index + 1, word) || // Up
                        dfs(board, r, c + 1, index + 1, word) || // Right
                        dfs(board, r, c - 1, index + 1, word);   // Left
                        
        // UNDO CHOICE: Restore the character for other recursive branches
        board[r][c] = temp;
        
        return found;
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N \times 3^L)$, where $L$ is the length of the word. We iterate through the $M \times N$ board. At each cell, we explore up to 3 directions (we don't go back where we came from).
• Space Complexity: $O(L)$ for the recursion stack.

5. Advanced Code Example: The N-Queens Problem

Problem Statement: (LeetCode 51) The n-queens puzzle is the problem of placing n queens on an $n \times n$ chessboard such that no two queens attack each other. Return all distinct solutions.

A Queen attacks in the same row, same column, and diagonals. To optimize, instead of trying to place queens anywhere on the board, we strictly place one queen per row.

import java.util.ArrayList;
import java.util.List;

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        
        // Initialize empty board
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        
        backtrack(result, board, 0, n);
        return result;
    }
    
    private void backtrack(List<List<String>> result, char[][] board, int row, int n) {
        // Base case: If we successfully placed a queen in every row!
        if (row == n) {
            result.add(construct(board));
            return;
        }
        
        // Try placing a queen in each column of the current row
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col, n)) {
                board[row][col] = 'Q'; // MAKE CHOICE
                backtrack(result, board, row + 1, n); // RECURSE to next row
                board[row][col] = '.'; // UNDO CHOICE
            }
        }
    }
    
    private boolean isSafe(char[][] board, int row, int col, int n) {
        // Check column (above us)
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // Check top-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // Check top-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true; // Safe!
    }
    
    // Helper to format the board for the final result
    private List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            res.add(new String(board[i]));
        }
        return res;
    }
}

Complexity Analysis:

• Time Complexity: $O(N!)$. For the first row, we have $N$ choices. For the second row, we have at most $N-1$ choices, etc.
• Space Complexity: $O(N^2)$ to store the board configuration.

6. Common Mistakes Beginners Make

1. Forgetting to UNDO the visited state

   • The Mistake: Marking a cell as visited, searching from it, but forgetting to un-mark it when returning false.
   • Why it's wrong: If you don't un-mark it, that cell becomes permanently blocked for ALL other recursive paths that might want to cross it later in the search.

2. Passing visited Arrays Incorrectly

   • The Mistake: Creating boolean[][] visited = new boolean[n][n] INSIDE the recursive function.
   • Why it's wrong: Every step of the recursion creates its own blank slate, completely destroying the purpose of tracking where you have been.
   • The Fix: Create the visited array in the wrapper function and pass the reference down.

3. Over-checking Boundaries (N-Queens)

   • The Mistake: In N-Queens, checking the bottom diagonals or the current row.
   • Why it's wrong: You are placing queens row by row from top to bottom. There are mathematically no queens below you, and no other queens in your current row. You only need to check upwards!

7. Interview Q&A

Q1: How do you optimize the isSafe check in N-Queens to be $O(1)$ instead of $O(N)$? Answer: We can use three HashSets (or boolean arrays): one to track columns, one to track the main diagonals (row - col), and one to track the anti-diagonals (row + col). This allows us to check if a spot is under attack instantly, reducing the overall time complexity significantly.

Q2: Sudoku Solver is a classic backtracking problem. What does the state tree look like? Answer: You scan the board for the first empty cell (.). That cell is a node in your tree, and it has 9 branches (try numbers 1-9). For every valid number, you recurse. If you reach the end of the board without failing, the board is solved. If you exhaust 1-9 and none work, you backtrack, erasing the cell, and go back to the previous empty cell.

Q3: (LeetCode 212) Word Search II: How do you find multiple words on a board efficiently? Answer: If you run normal Word Search for every word in a dictionary, it takes $O(W \times M \times N \times 3^L)$, which is too slow. The optimal solution is to build a Trie (Prefix Tree) out of the dictionary words. Then, as you explore the board, you simultaneously traverse the Trie. If a path on the board doesn't match any prefix in the Trie, you instantly prune the branch.

8. Practice Problems

1. Sudoku Solver (LeetCode 37)
   • Goal: Fill a 9x9 board.
   • Hint: Write a helper function isValid(board, row, col, char c) that checks the 3x3 sub-box, row, and column.
2. Path with Maximum Gold (LeetCode 1219)
   • Hint: This is exactly like Word Search, but instead of tracking characters, you maintain a running sum of integers. Use max = Math.max(max, dfs(...)) at each step.
3. Word Search II (LeetCode 212)
   • Hint: Combine Backtracking with a Trie data structure for a massive performance boost.

9. Summary

• Movement Array Strategy: For cleaner code in 4-directional grids, avoid writing 4 recursive calls. Instead use an array: int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}}; and use a for loop.
• In-Place Tracking: To save $O(N^2)$ space, don't allocate a boolean[][] visited. Just mutate the original board (e.g., change the character to #) and revert it during the backtrack phase.
• Pruning is King: Board problems explode to exponential times ($O(2^N)$, $O(3^N)$, $O(N!)$). The only reason they finish before the heat death of the universe is because we write strict boundary and validity checks that cut off useless paths early.