Problem
Given an integer n, return the number of distinct solutions to the N-Queens puzzle. The queens must be placed so that no two queens share the same row, column, or diagonal.Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 4Output
2Solution
This solution uses Backtracking to place one queen in each row. For every row, the algorithm tries every column and checks whether the position is safe.Three sets are used to track occupied positions:
columns stores used columns, diagonals stores positions identified by row - col, and antiDiagonals stores positions identified by row + col.
If a position is already occupied by another queen's column or diagonal, it is skipped. Otherwise, the queen is placed and the recursion moves to the next row.
When
row == n, all queens have been successfully placed, so one valid solution is found and the count is increased.
After returning from the recursive call, the queen is removed and its column and diagonal positions are removed from the sets. This allows the algorithm to try the next possible position.
public int totalNQueens(int n) {
return backtrack(n, 0, new HashSet<>(),
new HashSet<>(), new HashSet<>());
}
private int backtrack(int n, int row,
Set<Integer> columns,
Set<Integer> diagonals,
Set<Integer> antiDiagonals) {
// All queens are placed.
if (row == n) {
return 1;
}
int count = 0;
for (int col = 0; col < n; col++) {
int diagonal = row - col;
int antiDiagonal = row + col;
// Skip positions under attack.
if (columns.contains(col)
|| diagonals.contains(diagonal)
|| antiDiagonals.contains(antiDiagonal)) {
continue;
}
// Place the queen.
columns.add(col);
diagonals.add(diagonal);
antiDiagonals.add(antiDiagonal);
count += backtrack(n, row + 1, columns,
diagonals, antiDiagonals);
// Remove the queen and try the next position.
columns.remove(col);
diagonals.remove(diagonal);
antiDiagonals.remove(antiDiagonal);
}
return count;
}
Complexity
The algorithm explores possible queen placements row by row. In the worst case, the backtracking process can explore up toO(n!) arrangements because each row must use a different column.
The recursion depth is
O(n), and the three sets require O(n) space, excluding the recursion stack.