# 1. Problem set - Place $n$ queens on an $n \times n$ chessboard such that no two queens attack each other. - **Constraints**: - No two queens can share the same row. - No two queens can share the same column. - No two queens can share the same positive or negative diagonal. - Return all distinct configurations as a list of boards, where 'Q' represents a queen and '.' represents an empty space. - $1 \le n \le 9$ (standard competitive programming constraint for this problem). # 2. Methodology - **Logic**: Use a recursive backtracking approach to place queens row by row. For each row, iterate through all columns and validate the placement using lookup arrays for columns and both sets of diagonals. - **Algorithm**: Backtracking with pruning. - **Data Structure**: - `boolean[]` arrays for $O(1)$ collision detection. - `char[][]` for board state representation. - **Complexity**: - Time: $O(n!)$, as we explore permutations of columns while pruning invalid branches. - Space: $O(n^2)$ to store the board and result sets. # 3. Solution ```java import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class NQueensSolver { /** * Main entry point to solve the N-Queens puzzle. * @param n The size of the board and number of queens. * @return A list of all distinct board configurations. */ public List> solveNQueens(int n) { List> results = new ArrayList<>(); // Initialize the board with empty spots '.' char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(board[i], '.'); } // Boolean arrays to track occupied columns and diagonals in O(1) // cols: vertical check // diag1: top-left to bottom-right (row - col is constant) // diag2: top-right to bottom-left (row + col is constant) boolean[] cols = new boolean[n]; boolean[] diag1 = new boolean[2 * n]; boolean[] diag2 = new boolean[2 * n]; backtrack(0, n, board, results, cols, diag1, diag2); return results; } /** * Recursive backtracking function. */ private void backtrack(int row, int n, char[][] board, List> results, boolean[] cols, boolean[] diag1, boolean[] diag2) { // Base case: If we've placed queens in all rows, we found a solution if (row == n) { results.add(constructBoard(board)); return; } for (int col = 0; col < n; col++) { // Calculate indices for diagonals // id1: row - col offset by n to keep it positive // id2: row + col int id1 = row - col + n; int id2 = row + col; // Pruning: skip if column or diagonals are already occupied if (cols[col] || diag1[id1] || diag2[id2]) { continue; } // Place Queen board[row][col] = 'Q'; cols[col] = true; diag1[id1] = true; diag2[id2] = true; // Recurse to the next row backtrack(row + 1, n, board, results, cols, diag1, diag2); // Backtrack: remove Queen and reset occupancy tracking board[row][col] = '.'; cols[col] = false; diag1[id1] = false; diag2[id2] = false; } } /** * Converts the char[][] board into the required List of Strings format. */ private List constructBoard(char[][] board) { List currentBoard = new ArrayList<>(); for (int i = 0; i < board.length; i++) { // Create a string representation of the current row currentBoard.add(new String(board[i])); } return currentBoard; } public static void main(String[] args) { NQueensSolver solver = new NQueensSolver(); int n = 4; List> solutions = solver.solveNQueens(n); System.out.println("Solutions for n=" + n + ": " + solutions.size()); for (List sol : solutions) { for (String row : sol) { System.out.println(row); } System.out.println(); } } } ```