N-Queen
Problem link: https://leetcode.com/problems/n-queens/
Problem Statement
Place n queens on an n x n chessboard such that no two queens attack each other.
Return all distinct solutions, where each solution is a board of '.' and 'Q'.
Input
n: board size and number of queens
Output
- List of all valid boards
Example
n = 4
output = 2 solutions
Explanation
There are exactly 2 non-attacking configurations for n = 4.
Brute Force
Intuition
Try to place queens row by row; for each placement, check if it conflicts with earlier queens.
Approach
Backtrack row by row. To validate a placement, scan up-left, up-right, and up (column).
Code (Java)
Time: O(N! · N)Space: O(N^2)
Complexity Analysis
- Time ~
O(N! · N): backtracking explores permutations of columns; safety checks costO(N)by scanning. - Space
O(N^2): the board is stored as ann x ngrid.
Optimal Solution
Intuition
When you place a queen at (row, col), you block:
- the column
col - the main diagonal
(row - col) - the anti-diagonal
(row + col)
Hash these constraints to get O(1) safety checks.
Approach
Use boolean arrays for O(1) safety checks:
cols[c]diag1[row - col + (n - 1)]diag2[row + col]
Code (Java)
import java.util.ArrayList;
import java.util.List;
public class NQueensOptimal {
public static List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) board[r][c] = '.';
}
boolean[] cols = new boolean[n];
boolean[] diag1 = new boolean[2 * n - 1]; // row - col + (n - 1)
boolean[] diag2 = new boolean[2 * n - 1]; // row + col
List<List<String>> ans = new ArrayList<>();
backtrack(0, board, cols, diag1, diag2, ans);
return ans;
}
private static void backtrack(
int row,
char[][] board,
boolean[] cols,
boolean[] diag1,
boolean[] diag2,
List<List<String>> ans
) {
int n = board.length;
if (row == n) {
ans.add(toList(board));
return;
}
for (int col = 0; col < n; col++) {
int d1 = row - col + (n - 1);
int d2 = row + col;
if (cols[col] || diag1[d1] || diag2[d2]) continue;
cols[col] = diag1[d1] = diag2[d2] = true;
board[row][col] = 'Q';
backtrack(row + 1, board, cols, diag1, diag2, ans);
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
private static List<String> toList(char[][] board) {
List<String> out = new ArrayList<>();
for (char[] row : board) out.add(new String(row));
return out;
}
}
Time: O(N!)Space: O(N^2)
Complexity Analysis
- Time ~
O(N!): same backtracking search space, but safety checks are O(1). - Space
O(N^2): board plus O(N) hashing arrays.
Quick Revision (Brute Force)
- Backtrack row-by-row; validate by scanning column/diagonals each time.
- Safety check costs O(N) per placement attempt.
- Time ~O(N!·N), Space O(N^2).
Quick Revision (Optimal)
- Backtrack row-by-row; hash used cols/diagonals with boolean arrays.
- Safety check becomes O(1).
- Time ~O(N!), Space O(N^2).