Place n queens on an n x n chessboard such that no two queens attack each other (same row, column, or diagonal). Return all distinct solutions, each as a board configuration.
Example 1
Input: n = 4
Output: 2 solutions
Explanation: Two distinct ways to place 4 non-attacking queens on a 4x4 board.
1 <= n <= 9Place exactly one queen per row — this immediately eliminates the 'same row' conflict from ever being possible, cutting the search space dramatically.
For each row, try every column; a column or diagonal conflict with an already-placed queen means pruning that branch IMMEDIATELY, not waiting to discover the conflict later.
Track occupied columns and both diagonal directions (row-col and row+col are constant along each diagonal) with sets for O(1) conflict checks, rather than re-scanning all placed queens on every attempt.
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
int[] queenCol = new int[n]; // queenCol[row] = column of the queen in that row
Set<Integer> usedCols = new HashSet<>();
Set<Integer> usedDiag1 = new HashSet<>(); // row - col is constant along a '\' diagonal
Set<Integer> usedDiag2 = new HashSet<>(); // row + col is constant along a '/' diagonal
backtrack(0, n, queenCol, usedCols, usedDiag1, usedDiag2, result);
return result;
}
private void backtrack(int row, int n, int[] queenCol, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, List<List<String>> result) {
if (row == n) { result.add(buildBoard(queenCol, n)); return; }
for (int col = 0; col < n; col++) {
if (cols.contains(col) || d1.contains(row - col) || d2.contains(row + col)) continue; // PRUNE immediately
queenCol[row] = col;
cols.add(col); d1.add(row - col); d2.add(row + col);
backtrack(row + 1, n, queenCol, cols, d1, d2, result);
cols.remove(col); d1.remove(row - col); d2.remove(row + col); // UNCHOOSE
}
}
private List<String> buildBoard(int[] queenCol, int n) {
List<String> board = new ArrayList<>();
for (int row = 0; row < n; row++) {
char[] rowChars = new char[n];
Arrays.fill(rowChars, '.');
rowChars[queenCol[row]] = 'Q';
board.add(new String(rowChars));
}
return board;
}Time: O(n!) worst case, heavily pruned in practice · Space: O(n)