Advanced Backtracking: N-Queens and Sudoku

N-Queens Problem

The goal is to place $N$ queens on an $N \times N$ chessboard such that no two queens threaten each other (no same row, same column, or same diagonal).

Solution Strategy

Place queens row by row. For each row, select an available column. Use three sets to track occupied columns and both diagonal types:

• Column: Identical col index.
• Anti-Diagonal: Cells on the same anti-diagonal have a constant row - col.
• Diagonal: Cells on the same diagonal have a constant row + col.

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n]; // queens[row] = col
    Arrays.fill(queens, -1);
    
    // Sets to track occupied constraints
    Set<Integer> columns = new HashSet<>();
    Set<Integer> diag1 = new HashSet<>(); // row - col
    Set<Integer> diag2 = new HashSet<>(); // row + col
    
    backtrack(n, 0, queens, columns, diag1, diag2, res);
    return res;
}

private void backtrack(int n, int row, int[] queens, 
                       Set<Integer> columns, Set<Integer> diag1, Set<Integer> diag2, 
                       List<List<String>> res) {
    if (row == n) {
        res.add(generateBoard(queens, n));
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (columns.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) {
            continue; // Pruning: position threatened
        }
        
        // 1. Place Queen
        queens[row] = col;
        columns.add(col);
        diag1.add(row - col);
        diag2.add(row + col);
        
        // 2. Explore next row
        backtrack(n, row + 1, queens, columns, diag1, diag2, res);
        
        // 3. Backtrack
        queens[row] = -1;
        columns.remove(col);
        diag1.remove(row - col);
        diag2.remove(row + col);
    }
}

Complexity: Overly $O(N!)$ time, $O(N)$ space.

Sudoku Solver

Fill a $9 \times 9$ grid so that every row, column, and $3 \times 3$ sub-grid contains digits 1-9 without repetition.

Solution Strategy

Traverse every cell. If empty, try digits 1-9. If a valid digit is found, recurse to the next cell. If no digits work, backtrack.

public void solveSudoku(char[][] board) {
    backtrack(board);
}

private boolean backtrack(char[][] board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;
            
            for (char num = '1'; num <= '9'; num++) {
                if (isValid(board, r, c, num)) {
                    board[r][c] = num;
                    if (backtrack(board)) return true; // Solution found!
                    board[r][c] = '.'; // Backtrack
                }
            }
            return false; // Exhausted 1-9 for this cell
        }
    }
    return true; // All cells filled
}

private boolean isValid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == c) return false; // Check row
        if (board[i][col] == c) return false; // Check column
        // Check 3x3 block
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
    }
    return true;
}

Word Search (LeetCode 79)

Search for a contiguous sequence of letters in a grid that matches a target word.

public boolean exist(char[][] board, String word) {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (dfs(board, word, r, c, 0)) return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int r, int c, int index) {
    if (index == word.length()) return true;
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) {
        return false;
    }
    
    char temp = board[r][c];
    board[r][c] = '#'; // Mark as visited
    
    boolean found = dfs(board, word, r + 1, c, index + 1) ||
                    dfs(board, word, r - 1, c, index + 1) ||
                    dfs(board, word, r, c + 1, index + 1) ||
                    dfs(board, word, r, c - 1, index + 1);
                    
    board[r][c] = temp; // Restore (Backtrack)
    return found;
}

Pruning Summary Table