Problem
Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution must place exactly n queens on an n Ć n chessboard 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 = 4 Output
[ [".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."] ]
Arrangement 1 Arrangement 2
+---+---+---+---+ +---+---+---+---+
| . | Q | . | . | | . | . | Q | . |
+---+---+---+---+ +---+---+---+---+
| . | . | . | Q | | Q | . | . | . |
+---+---+---+---+ +---+---+---+---+
| Q | . | . | . | | . | . | . | Q |
+---+---+---+---+ +---+---+---+---+
| . | . | Q | . | | . | Q | . | . |
+---+---+---+---+ +---+---+---+---+
Solution
This solution uses Backtracking and places one queen in each row. For every row, we try each column and check whether placing a queen there is safe.A position is invalid if another queen already exists in the same column, main diagonal, or anti-diagonal. These positions are tracked using three HashSet objects for fast lookup.
If a valid position is found, the queen is placed and the algorithm moves to the next row. When all rows are filled, the current board is added to the result.
After exploring that path, the queen is removed so that other possible positions can be explored.
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0, board, new HashSet<>(), new HashSet<>(),
new HashSet<>(), result);
return result;
}
private void backtrack(int row, char[][] board,
Set<Integer> columns, Set<Integer> diagonals,
Set<Integer> antiDiagonals, List<List<String>> result) {
// All queens are placed.
if (row == board.length) {
List<String> solution = new ArrayList<>();
for (char[] currentRow : board) {
solution.add(new String(currentRow));
}
result.add(solution);
return;
}
for (int col = 0; col < board.length; 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.
board[row][col] = 'Q';
columns.add(col);
diagonals.add(diagonal);
antiDiagonals.add(antiDiagonal);
backtrack(row + 1, board, columns, diagonals,
antiDiagonals, result);
// Remove the queen and try the next position.
board[row][col] = '.';
columns.remove(col);
diagonals.remove(diagonal);
antiDiagonals.remove(antiDiagonal);
}
}
Complexity
The algorithm explores possible queen placements recursively. The number of valid arrangements grows rapidly as n increases, and the worst-case time complexity is approximatelyO(n!).
The board, sets, and recursion stack require
O(nĀ²) space, mainly because the board itself contains nĀ² cells.