# 1. Problem set - Place $n$ queens on an $n \times n$ chessboard such that no two queens attack each other. - Two queens attack each other if they share the same row, column, or diagonal. - Output all distinct solutions where each solution contains a specific board configuration. - Constraints: $1 \le n \le 9$. # 2. Methodology - **Algorithm**: Backtracking with pruning. We iterate row by row, attempting to place a queen in each column. - **Data Structure**: - `boolean[]` arrays to track occupied columns, positive diagonals ($row + col$), and negative diagonals ($row - col$). - `char[][]` to represent the board. - **Complexity**: - **Time**: $O(N!)$ - In the first row we have $N$ choices, then roughly $N-2$ in the next, etc. - **Space**: $O(N^2)$ to store the board and recursion stack. # 3. Solution ```java import java.util.ArrayList; import java.util.List; public class Solution { public List> solveNQueens(int n) { // Result list to store all valid board configurations List> results = new ArrayList<>(); // Initialize board with empty cells '.' char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { board[i][j] = '.'; } } // Boolean arrays to track occupied paths in O(1) time boolean[] cols = new boolean[n]; boolean[] diag1 = new boolean[2 * n]; // row + col boolean[] diag2 = new boolean[2 * n]; // row - col + n (offset to avoid negative) backtrack(0, n, board, results, cols, diag1, diag2); return results; } private void backtrack(int row, int n, char[][] board, List> results, boolean[] cols, boolean[] diag1, boolean[] diag2) { // Base case: If we placed queens in all rows, add current board to results if (row == n) { results.add(construct(board)); return; } for (int col = 0; col < n; col++) { // Calculate diagonal indices int d1 = row + col; int d2 = row - col + n; // Check if column or diagonals are already occupied if (cols[col] || diag1[d1] || diag2[d2]) { continue; } // Place queen board[row][col] = 'Q'; cols[col] = true; diag1[d1] = true; diag2[d2] = true; // Move to the next row backtrack(row + 1, n, board, results, cols, diag1, diag2); // Backtrack: Remove queen and reset state board[row][col] = '.'; cols[col] = false; diag1[d1] = false; diag2[d2] = false; } } // Helper method to convert char[][] board to List of Strings private List construct(char[][] board) { List res = new ArrayList<>(); for (int i = 0; i < board.length; i++) { res.add(new String(board[i])); } return res; } } ```