N-Queens
The n-queens puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other. Given an integer `n`, return all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space, respectively.
Examples
Constraints
1 <= n <= 9
Backtracking with Sets
Approach
We place queens row by row. For a given row, we try placing a queen in each column. To check if a placement is valid, we must ensure no other queen shares the same column, positive diagonal (row + col), or negative diagonal (row - col). We use three hash sets to keep track of columns and diagonals that are under attack. If a placement is valid, we add it to our board state and move to the next row. Once we successfully place `n` queens, we add the board configuration to our results.
Complexity Analysis
The time complexity is loosely bounded by O(n!). In reality, it is much faster due to the pruning of invalid placements. The space complexity is O(n^2) to store the board state and O(n) for the sets and recursion stack.
class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); // Sets to track which columns and diagonals are occupied Set<Integer> cols = new HashSet<>(); Set<Integer> posDiag = new HashSet<>(); // row + col Set<Integer> negDiag = new HashSet<>(); // row - col // Initialize an empty board char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(board[i], '.'); } backtrack(0, n, cols, posDiag, negDiag, board, result); return result; } private void backtrack(int r, int n, Set<Integer> cols, Set<Integer> posDiag, Set<Integer> negDiag, char[][] board, List<List<String>> result) { // Base case: all queens are placed if (r == n) { List<String> validBoard = new ArrayList<>(); for (int i = 0; i < n; i++) { validBoard.add(new String(board[i])); } result.add(validBoard); return; } // Try placing a queen in each column of the current row for (int c = 0; c < n; c++) { if (cols.contains(c) || posDiag.contains(r + c) || negDiag.contains(r - c)) { continue; // Cannot place queen here } // Place the queen cols.add(c); posDiag.add(r + c); negDiag.add(r - c); board[r][c] = 'Q'; // Move to the next row backtrack(r + 1, n, cols, posDiag, negDiag, board, result); // Backtrack: remove the queen cols.remove(c); posDiag.remove(r + c); negDiag.remove(r - c); board[r][c] = '.'; } }}