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>> solveNQueensNaive(int n) {
List<List<String>> result = new ArrayList<>();
int[] queenCol = new int[n];
backtrack(0, n, queenCol, result);
return result;
}
private void backtrack(int row, int n, int[] queenCol, List<List<String>> result) {
if (row == n) { result.add(buildBoard(queenCol, n)); return; }
for (int col = 0; col < n; col++) {
if (isSafe(queenCol, row, col)) { // O(row) check against every previously placed queen
queenCol[row] = col;
backtrack(row + 1, n, queenCol, result);
}
}
}
private boolean isSafe(int[] queenCol, int row, int col) {
for (int r = 0; r < row; r++) {
int c = queenCol[r];
if (c == col || Math.abs(c - col) == Math.abs(r - row)) return false; // same column or same diagonal
}
return true;
}
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! * n) roughly — the extra factor of n from the linear safety check · Space: O(n)