N-Queens (LeetCode
Learn how to solve the N-Queens problem using backtracking, board validation, column and diagonal checks, pruning, and recursion. Includes intuition, a 4x4 dry run, Java code, complexity analysis, common mistakes, and interview tips.
Introduction
The N-Queens problem is one of the most important constraint-based backtracking problems.
It is frequently discussed in interviews at companies such as:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Bloomberg
- Goldman Sachs
- JPMorgan Chase
The problem tests whether you can:
- Model a search space
- Place one decision at a time
- Validate constraints
- Prune invalid branches early
- Restore mutable state
- Represent a board efficiently
- Analyze exponential algorithms
- Explain recursive search clearly
N-Queens is a natural progression after learning:
- Subsets
- Permutations
- Combinations
- Combination Sum
In those problems, most choices were valid.
In N-Queens, many choices are invalid because queens attack each other.
The essential backtracking pattern remains:
graph TD
Choose["Choose"] --> Validate["Validate"]
Validate["Validate"] --> Explore["Explore"]
Explore["Explore"] --> Unchoose["Unchoose"]
Problem Statement
Place n queens on an n × n chessboard so that no two queens attack each other.
Return all distinct valid board configurations.
A queen can attack another queen in:
- The same row
- The same column
- The same diagonal
Example 1
Input
n = 4
Output
[
[
".Q..",
"...Q",
"Q...",
"..Q."
],
[
"..Q.",
"Q...",
"...Q",
".Q.."
]
]
There are exactly two valid solutions for a 4 × 4 board.
Example 2
Input
n = 1
Output
[
[
"Q"
]
]
A single queen is always valid on a 1 × 1 board.
What Does a Valid Board Mean?
A valid board must satisfy all three constraints.
No Two Queens in the Same Row
Invalid:
Q Q . .
Two queens appear in the same row.
No Two Queens in the Same Column
Invalid:
Q . . .
Q . . .
. . . .
. . . .
Both queens occupy column 0.
No Two Queens on the Same Diagonal
Invalid:
Q . . .
. Q . .
. . . .
. . . .
The queens share the main diagonal.
Why Place One Queen per Row?
A valid solution requires exactly n queens.
Since two queens cannot share a row, every row must contain exactly one queen.
Therefore, instead of trying every board cell independently, the algorithm can process one row at a time.
At each row:
- Try each column.
- Check whether the position is safe.
- Place the queen.
- Recurse to the next row.
- Remove the queen.
This reduces the search space significantly.
Core Backtracking State
The recursive state includes:
- Current row
- Current board
- Previously placed queens
- Completed solutions
At recursion row r, all rows before r are already valid.
The algorithm only needs to find a safe column for row r.
Backtracking Decision
For every row:
Try Column 0
Try Column 1
Try Column 2
...
Try Column n - 1
For each column:
Safe?
No → Skip
Yes → Place Queen
Recurse to Next Row
Remove Queen
Choose–Explore–Unchoose
Choose
board[row][column] = 'Q';
Place a queen.
Explore
backtrack(
row + 1,
board,
result);
Continue with the next row.
Unchoose
board[row][column] = '.';
Remove the queen before trying another column.
Base Condition
When:
row == n
all rows have been processed successfully.
This means:
- One queen is placed in every row.
- No two queens share a column.
- No two queens share a diagonal.
Convert the board into strings and save the solution.
Why Is N-Queens a Backtracking Problem?
The algorithm must explore different queen placements.
A placement that appears valid initially may cause a conflict later.
Example:
graph TD
Place_Queen_in_Row_0["Place Queen in Row 0"] --> Place_Queen_in_Row_1["Place Queen in Row 1"]
Place_Queen_in_Row_1["Place Queen in Row 1"] --> Place_Queen_in_Row_2["Place Queen in Row 2"]
Place_Queen_in_Row_2["Place Queen in Row 2"] --> No_Safe_Position_in_Row_3["No Safe Position in Row 3"]
The algorithm must return to an earlier row, remove a queen, and try another position.
That is exactly what backtracking does.
Brute Force Approach
Idea
An n × n board contains:
n²
cells.
A naive approach could choose any n cells and test whether they form a valid arrangement.
The number of possible choices is:
C(n², n)
This becomes enormous very quickly.
Another brute-force method places one queen per row but tries every column arrangement.
There are:
n^n
possible row-to-column assignments.
Example for n = 8:
8^8
=
16,777,216
Many of these arrangements repeat columns and are immediately invalid.
Backtracking avoids exploring invalid branches deeply.
Improved Search Space
Since each row has exactly one queen and no two queens can share a column, each solution corresponds to a permutation of columns.
The search space becomes at most:
n!
before diagonal pruning.
For n = 8:
8!
=
40,320
Diagonal validation prunes many of these branches even earlier.
Board Representation
A convenient board representation is:
char[][] board
Initialize every cell with:
'.'
Place a queen using:
'Q'
Example:
[
['.', 'Q', '.', '.'],
['.', '.', '.', 'Q'],
['Q', '.', '.', '.'],
['.', '.', 'Q', '.']
]
Convert each row into a string before adding the completed board to the output.
Board Initialization
char[][] board =
new char[n][n];
for (char[] row : board) {
Arrays.fill(
row,
'.');
}
Approach 1 — Basic Backtracking with Board Scanning
Core Idea
Process rows from top to bottom.
For every column in the current row:
- Check whether a queen can safely be placed.
- Place it.
- Recurse.
- Remove it.
The safety check scans:
- The same column above
- The upper-left diagonal
- The upper-right diagonal
There is no need to scan the current row because the algorithm places only one queen per row.
There is no need to scan rows below because they have not been processed yet.
Java Code — Basic Solution
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NQueens {
public List<List<String>> solveNQueens(
int n) {
if (n <= 0) {
return List.of();
}
List<List<String>> result =
new ArrayList<>();
char[][] board =
new char[n][n];
for (char[] row : board) {
Arrays.fill(
row,
'.');
}
backtrack(
0,
board,
result);
return result;
}
private void backtrack(
int row,
char[][] board,
List<List<String>> result) {
if (row == board.length) {
result.add(
buildBoard(board));
return;
}
for (int column = 0;
column < board.length;
column++) {
if (!isSafe(
board,
row,
column)) {
continue;
}
board[row][column] = 'Q';
backtrack(
row + 1,
board,
result);
board[row][column] = '.';
}
}
private boolean isSafe(
char[][] board,
int row,
int column) {
return isColumnSafe(
board,
row,
column)
&& isUpperLeftDiagonalSafe(
board,
row,
column)
&& isUpperRightDiagonalSafe(
board,
row,
column);
}
private boolean isColumnSafe(
char[][] board,
int row,
int column) {
for (int currentRow = 0;
currentRow < row;
currentRow++) {
if (board[currentRow][column]
== 'Q') {
return false;
}
}
return true;
}
private boolean isUpperLeftDiagonalSafe(
char[][] board,
int row,
int column) {
int currentRow = row - 1;
int currentColumn = column - 1;
while (currentRow >= 0
&& currentColumn >= 0) {
if (board[currentRow][currentColumn]
== 'Q') {
return false;
}
currentRow--;
currentColumn--;
}
return true;
}
private boolean isUpperRightDiagonalSafe(
char[][] board,
int row,
int column) {
int currentRow = row - 1;
int currentColumn = column + 1;
while (currentRow >= 0
&& currentColumn < board.length) {
if (board[currentRow][currentColumn]
== 'Q') {
return false;
}
currentRow--;
currentColumn++;
}
return true;
}
private List<String> buildBoard(
char[][] board) {
List<String> result =
new ArrayList<>(
board.length);
for (char[] row : board) {
result.add(
new String(row));
}
return result;
}
}
Compact Basic Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NQueensCompact {
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,
'.');
}
placeQueens(
0,
board,
result);
return result;
}
private void placeQueens(
int row,
char[][] board,
List<List<String>> result) {
if (row == board.length) {
result.add(
convert(board));
return;
}
for (int column = 0;
column < board.length;
column++) {
if (!isSafe(
board,
row,
column)) {
continue;
}
board[row][column] = 'Q';
placeQueens(
row + 1,
board,
result);
board[row][column] = '.';
}
}
private boolean isSafe(
char[][] board,
int row,
int column) {
for (int currentRow = 0;
currentRow < row;
currentRow++) {
if (board[currentRow][column]
== 'Q') {
return false;
}
}
for (int currentRow = row - 1,
currentColumn = column - 1;
currentRow >= 0
&& currentColumn >= 0;
currentRow--,
currentColumn--) {
if (board[currentRow][currentColumn]
== 'Q') {
return false;
}
}
for (int currentRow = row - 1,
currentColumn = column + 1;
currentRow >= 0
&& currentColumn
< board.length;
currentRow--,
currentColumn++) {
if (board[currentRow][currentColumn]
== 'Q') {
return false;
}
}
return true;
}
private List<String> convert(
char[][] board) {
List<String> configuration =
new ArrayList<>(
board.length);
for (char[] row : board) {
configuration.add(
new String(row));
}
return configuration;
}
}
Safety Check Explained
Suppose the algorithm wants to place a queen at:
row = 3
column = 2
It checks only previously processed rows.
Column Check
Inspect:
(0,2)
(1,2)
(2,2)
If any cell contains Q, the position is invalid.
Upper-Left Diagonal Check
Inspect:
(2,1)
(1,0)
The pattern is:
row--
column--
Upper-Right Diagonal Check
Inspect:
(2,3)
The pattern is:
row--
column++
Why Not Check the Lower Diagonals?
Rows below the current row are empty.
Queens are placed from top to bottom.
Therefore, only previous rows can contain conflicts.
Why Not Check the Current Row?
The algorithm processes one row at a time and places at most one queen before moving to the next row.
Therefore, a row conflict cannot occur.
Detailed Dry Run for n = 4
The 4 × 4 board has two valid solutions.
We will trace the first solution:
.Q..
...Q
Q...
..Q.
Column positions by row:
Row 0 → Column 1
Row 1 → Column 3
Row 2 → Column 0
Row 3 → Column 2
Initial Board
. . . .
. . . .
. . . .
. . . .
Start:
row = 0
Every column is initially safe.
First Attempt — Row 0, Column 0
Place:
Q . . .
. . . .
. . . .
. . . .
Recurse to row 1.
Row 1
Column 0
Invalid because column 0 already contains a queen.
Column 1
Invalid because it is diagonally below the queen at (0,0).
Column 2
Safe.
Place:
Q . . .
. . Q .
. . . .
. . . .
Recurse to row 2.
Row 2 After Positions (0,0) and (1,2)
Try each column.
Column 0
Invalid due to column conflict.
Column 1
Invalid due to diagonal conflict with (1,2).
Column 2
Invalid due to column conflict.
Column 3
Invalid due to diagonal conflict with (1,2).
No safe position exists.
Backtrack.
Remove queen from (1,2).
Row 1, Column 3
Place:
Q . . .
. . . Q
. . . .
. . . .
Recurse to row 2.
Row 2, Column 0
Invalid due to column conflict with (0,0).
Row 2, Column 1
Safe.
Place:
Q . . .
. . . Q
. Q . .
. . . .
Recurse to row 3.
Row 3
Column 0
Invalid due to column conflict.
Column 1
Invalid due to column conflict.
Column 2
Invalid due to diagonal conflict.
Column 3
Invalid due to column conflict.
No solution.
Backtrack repeatedly.
The branch beginning with row 0, column 0 produces no valid board.
Second Root Attempt — Row 0, Column 1
Place:
. Q . .
. . . .
. . . .
. . . .
Recurse to row 1.
Row 1, Column 0
Invalid due to diagonal conflict.
Row 1, Column 1
Invalid due to column conflict.
Row 1, Column 2
Invalid due to diagonal conflict.
Row 1, Column 3
Safe.
Place:
. Q . .
. . . Q
. . . .
. . . .
Recurse to row 2.
Row 2, Column 0
Safe.
Place:
. Q . .
. . . Q
Q . . .
. . . .
Recurse to row 3.
Row 3
Column 0
Invalid due to column conflict.
Column 1
Invalid due to column conflict.
Column 2
Safe.
Place:
. Q . .
. . . Q
Q . . .
. . Q .
Now:
row = 4
Since:
row == n
save the board.
First valid solution:
[
".Q..",
"...Q",
"Q...",
"..Q."
]
Backtracking After First Solution
After saving the solution:
- Remove the queen from row
3, column2. - Continue checking remaining columns in row
3. - Return to row
2. - Remove its queen.
- Continue the search.
Eventually, another root branch produces the second valid solution:
[
"..Q.",
"Q...",
"...Q",
".Q.."
]
First Solution Path
Row 0 → Column 1
Row 1 → Column 3
Row 2 → Column 0
Row 3 → Column 2
Represented as:
[1,3,0,2]
Second Solution Path
Row 0 → Column 2
Row 1 → Column 0
Row 2 → Column 3
Row 3 → Column 1
Represented as:
[2,0,3,1]
Partial Recursion Tree for n = 4
graph TD
Row_0_0["Row"] --> C0_1_1["C0"]
Row_0_0["Row"] --> C1_1_2["C1"]
N_0_0_1["0"] --> C2_1_3["C2"]
N_0_0_1["0"] --> C3_1_4["C3"]
C0_1_1["C0"] --> Row_2_1["Row"]
C0_1_1["C0"] --> N_1_2_2["1"]
C1_1_2["C1"] --> Row_2_3["Row"]
C1_1_2["C1"] --> N_1_2_4["1"]
Row_2_1["Row"] --> C3_3_1["C3"]
Row_2_1["Row"] --> C0_3_2["C0"]
C3_3_1["C3"] --> C0_4_1["C0"]
C3_3_1["C3"] --> C3_4_2["C3"]
C0_4_1["C0"] --> C2_5_1["C2"]
C0_4_1["C0"] --> C1_5_2["C1"]
C2_5_1["C2"] --> Solution_6_1["Solution"]
C2_5_1["C2"] --> N_1_6_2["1"]
C1_5_2["C1"] --> Solution_6_3["Solution"]
C1_5_2["C1"] --> N_2_6_4["2"]
Many branches are omitted because they are pruned immediately by safety checks.
Board Conversion
The internal board uses:
char[][]
But the required output type is:
List<List<String>>
Conversion:
private List<String> buildBoard(
char[][] board) {
List<String> configuration =
new ArrayList<>();
for (char[] row : board) {
configuration.add(
new String(row));
}
return configuration;
}
Each string is a snapshot of one board row.
Why Creating Strings Is Safe
This statement:
new String(row)
creates a new immutable string.
Later changes to the board do not modify already saved strings.
If mutable row arrays were stored directly, later backtracking would corrupt previous solutions.
Complexity Analysis
The exact runtime is difficult to express tightly because pruning depends on queen conflicts.
A common upper bound is:
O(n!)
Why?
- The first row has up to
nchoices. - The second row has at most
n - 1columns available. - The third row has at most
n - 2. - This resembles column permutations.
However, the basic implementation performs safety scanning for each attempted position.
Each safety check may cost:
O(n)
Therefore, a practical upper-bound description for the board-scanning implementation is:
O(n × n!)
or sometimes:
O(n² × n!)
when including board-copy costs and all checks conservatively.
Output Cost
Each completed solution contains:
n strings
Each string contains:
n characters
Copying one board costs:
O(n²)
If there are S solutions, output construction costs:
O(S × n²)
Space Complexity
Board
O(n²)
Recursion Stack
One recursive call per row:
O(n)
Output
If there are S solutions:
O(S × n²)
Complexity Summary
| Complexity | Basic Board-Scanning Solution |
|---|---|
| Search Time | Approximately O(n × n!) upper bound |
| Board Snapshot Cost | O(S × n²) |
| Board Space | O(n²) |
| Recursion Stack | O(n) |
| Output Space | O(S × n²) |
The optimized solution in Part 2 reduces each safety check from O(n) to O(1).
Why Backtracking Is Better Than Brute Force
Brute force generates complete boards and validates them afterward.
Backtracking validates every queen placement before going deeper.
Example:
graph TD
Row_0_Queen["Row 0 Queen"] --> Row_1_Conflict["Row 1 Conflict"]
Row_1_Conflict["Row 1 Conflict"] --> Stop_Immediately["Stop Immediately"]
It does not continue placing queens in rows 2, 3, and beyond for an already invalid branch.
This is called pruning.
Pruning in N-Queens
The safety check is itself a pruning rule.
Before recursion:
if (!isSafe(
board,
row,
column)) {
continue;
}
An invalid placement is rejected immediately.
The earlier a branch is rejected, the more work is avoided.
Correctness Intuition
The algorithm is correct because:
- It processes each row exactly once.
- It tries every column in that row.
- It places a queen only when the column and both diagonals are safe.
- It removes the queen after exploring the branch.
- It saves a board only after all rows contain a queen.
- Every valid arrangement corresponds to exactly one sequence of column choices.
Therefore, every returned board is valid, and every valid board is eventually explored.
Formal Correctness Argument
At recursive call:
backtrack(row)
assume rows:
0 through row - 1
contain non-attacking queens.
For each candidate column in row:
- The safety check verifies that the new queen does not attack any earlier queen.
- Therefore, after placement, rows
0throughrowremain valid. - Recursion preserves this invariant.
When:
row == n
all n rows contain one non-attacking queen.
Thus the board is a valid solution.
Because every safe column is tried at every row, no valid configuration is omitted.
Common Interview Mistakes
Mistake 1 — Forgetting to Remove the Queen
Incorrect:
board[row][column] = 'Q';
backtrack(...);
Missing:
board[row][column] = '.';
Without state restoration, queens from previous branches remain on the board.
Mistake 2 — Checking the Entire Board
Scanning every cell for every placement is unnecessary.
Only check:
- The column above
- Upper-left diagonal
- Upper-right diagonal
Mistake 3 — Checking Lower Rows
Lower rows are still empty.
There is no need to inspect them.
Mistake 4 — Placing Multiple Queens in One Row
The recursive structure should process one row at a time.
Do not independently choose arbitrary board cells.
Mistake 5 — Saving the Mutable Board Directly
The board is reused during backtracking.
Convert it into new strings before storing it.
Mistake 6 — Incorrect Diagonal Movement
Upper-left:
row--
column--
Upper-right:
row--
column++
Mixing these directions leads to missed conflicts.
Mistake 7 — Off-by-One Boundary Errors
Correct diagonal loop conditions:
currentRow >= 0
and:
currentColumn >= 0
or:
currentColumn < n
Mistake 8 — Claiming O(n²) Time
The board has n² cells, but the algorithm explores many possible queen arrangements.
The search is exponential or factorial in nature.
Mistake 9 — Not Explaining Pruning
The main benefit of backtracking is that invalid boards are rejected before they are completed.
Mistake 10 — Returning After the First Solution
LeetCode #51 asks for all solutions.
Do not stop after finding one board.
A separate variation can return only the first solution.
Input Edge Cases
n = 1
One solution:
Q
n = 2
No solution exists.
[]
Any two queens attack each other.
n = 3
No solution exists.
[]
n = 4
Two solutions exist.
n <= 0
The coding problem normally provides positive n.
Production code should define a clear policy.
Possible behavior:
Return empty result
or:
Throw IllegalArgumentException
Basic Production-Style Validation
public List<List<String>> solveNQueens(
int n) {
if (n < 1) {
throw new IllegalArgumentException(
"Board size must be positive");
}
// Continue solving
}
For LeetCode compatibility, returning an empty result may be simpler.
N-Queens as a Constraint Satisfaction Problem
N-Queens can be modeled as a constraint satisfaction problem.
Variables
Each row has one variable:
column[row]
Domain
Each variable can take values:
0 through n - 1
Constraints
For rows r1 and r2:
Different Columns
column[r1] != column[r2]
Different Diagonals
abs(column[r1] - column[r2])
!=
abs(r1 - r2)
Backtracking assigns one variable at a time and rejects values that violate constraints.
Alternative One-Dimensional Representation
Instead of storing the full board during search, store:
int[] queenColumnByRow
Example:
[1,3,0,2]
means:
Row 0 → Column 1
Row 1 → Column 3
Row 2 → Column 0
Row 3 → Column 2
This requires only:
O(n)
search-state memory.
The board can be created only when a complete solution is found.
The optimized versions in Part 2 build on this idea.
Basic One-Dimensional Validation
A queen at:
(row, column)
conflicts with a previous queen at:
(previousRow, previousColumn)
when:
previousColumn == column
or:
abs(previousRow - row)
==
abs(previousColumn - column)
Java Code — One-Dimensional Basic Solution
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NQueensPositions {
public List<List<String>> solveNQueens(
int n) {
List<List<String>> result =
new ArrayList<>();
int[] positions =
new int[n];
Arrays.fill(
positions,
-1);
backtrack(
0,
positions,
result);
return result;
}
private void backtrack(
int row,
int[] positions,
List<List<String>> result) {
if (row == positions.length) {
result.add(
buildBoard(positions));
return;
}
for (int column = 0;
column < positions.length;
column++) {
if (!isSafe(
row,
column,
positions)) {
continue;
}
positions[row] = column;
backtrack(
row + 1,
positions,
result);
positions[row] = -1;
}
}
private boolean isSafe(
int row,
int column,
int[] positions) {
for (int previousRow = 0;
previousRow < row;
previousRow++) {
int previousColumn =
positions[previousRow];
if (previousColumn == column) {
return false;
}
int rowDistance =
row - previousRow;
int columnDistance =
Math.abs(
column
- previousColumn);
if (rowDistance
== columnDistance) {
return false;
}
}
return true;
}
private List<String> buildBoard(
int[] positions) {
List<String> board =
new ArrayList<>(
positions.length);
for (int row = 0;
row < positions.length;
row++) {
char[] boardRow =
new char[positions.length];
Arrays.fill(
boardRow,
'.');
boardRow[positions[row]] =
'Q';
board.add(
new String(boardRow));
}
return board;
}
}
Board Representation Comparison
Full char[][] Board |
One-Dimensional Positions |
|---|---|
| Easy to visualize | More memory-efficient |
| O(n²) search state | O(n) search state |
| Direct placement and removal | Stores only queen columns |
| Safety check scans board | Safety check scans earlier rows |
| Good for teaching | Good intermediate optimization |
The HashSet and boolean-array approaches in Part 2 provide O(1) safety checks.
Production Applications
N-Queens itself is primarily an educational puzzle, but its search pattern appears in real systems.
Examples include:
- Constraint-based scheduling
- Resource allocation
- Frequency assignment
- Seating arrangement
- Placement optimization
- Conflict-free task assignment
- Puzzle solving
- Test configuration generation
- Register allocation concepts
- Layout planning
Real-World Example — Meeting Scheduling
Suppose several meetings must be assigned to time slots.
Constraints may include:
- Two meetings cannot use the same room.
- Related teams cannot overlap.
- Certain sessions must not be adjacent.
- Some speakers are unavailable at specific times.
Like N-Queens, the algorithm:
- Assigns one item at a time.
- Checks constraints.
- Continues when valid.
- Backtracks when no valid assignment remains.
Real-World Example — Wireless Frequency Assignment
Transmitters must be assigned frequencies.
Nearby transmitters cannot share conflicting channels.
Each assignment resembles placing a queen:
- Variable: transmitter
- Domain: frequency
- Constraint: nearby transmitters must not conflict
Real systems often use graph-coloring or constraint solvers, but the backtracking idea is similar.
Real-World Example — Seating Arrangements
Guests must be placed at tables with constraints such as:
- Certain guests cannot sit together.
- Some guests must be near each other.
- Table capacity is limited.
- Department distribution must remain balanced.
The algorithm explores placements and rejects invalid partial arrangements early.
Backtracking Interview Explanation
A strong interview explanation could be:
I place exactly one queen in each row. For the current row, I try every column and check whether another queen exists in the same column or either upper diagonal. If the position is safe, I place the queen and recurse to the next row. After the recursive call, I remove the queen so the next column can be tested. When the row index reaches
n, every row contains a valid queen, so I convert the board into strings and save it. The search is roughly factorial because column choices shrink as queens are placed, and pruning removes diagonal conflicts early.
Interview Tips
Interviewers commonly ask:
- Why place one queen per row?
- Why do you check only upper directions?
- Why is a column check required?
- How are diagonals detected?
- Why must the queen be removed after recursion?
- What is the base condition?
- Why is this a backtracking problem?
- What is the approximate time complexity?
- How can safety checks be optimized?
- How would you return only the number of solutions?
- How would you return only one solution?
- How would you reduce board memory?
- Can symmetry reduce the search?
- Can bit manipulation solve the problem?
- How would you parallelize the first-row branches?
Unit Tests — Basic Solution
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.Test;
class NQueensTest {
private final NQueens solution =
new NQueens();
@Test
void shouldFindTwoSolutionsForFourQueens() {
List<List<String>> result =
solution.solveNQueens(4);
assertEquals(
2,
result.size());
assertTrue(
result.contains(
List.of(
".Q..",
"...Q",
"Q...",
"..Q.")));
assertTrue(
result.contains(
List.of(
"..Q.",
"Q...",
"...Q",
".Q..")));
}
@Test
void shouldFindOneSolutionForOneQueen() {
List<List<String>> result =
solution.solveNQueens(1);
assertEquals(
List.of(
List.of("Q")),
result);
}
@Test
void shouldFindNoSolutionForTwoQueens() {
List<List<String>> result =
solution.solveNQueens(2);
assertTrue(
result.isEmpty());
}
@Test
void shouldFindNoSolutionForThreeQueens() {
List<List<String>> result =
solution.solveNQueens(3);
assertTrue(
result.isEmpty());
}
}
Unit Test — Validate Every Returned Board
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.junit.jupiter.api.Test;
class NQueensBoardValidationTest {
private final NQueens solution =
new NQueens();
@Test
void everyReturnedBoardShouldBeValid() {
List<List<String>> boards =
solution.solveNQueens(5);
for (List<String> board : boards) {
assertValid(board);
}
}
private void assertValid(
List<String> board) {
int n = board.size();
Set<Integer> columns =
new HashSet<>();
Set<Integer> descendingDiagonals =
new HashSet<>();
Set<Integer> ascendingDiagonals =
new HashSet<>();
int queenCount = 0;
for (int row = 0;
row < n;
row++) {
for (int column = 0;
column < n;
column++) {
if (board.get(row)
.charAt(column)
!= 'Q') {
continue;
}
queenCount++;
assertFalse(
!columns.add(column));
assertFalse(
!descendingDiagonals.add(
row - column));
assertFalse(
!ascendingDiagonals.add(
row + column));
}
}
assertEquals(
n,
queenCount);
}
}
N-Queens (LeetCode #51) — Part 2
Optimizing the Safety Check
The basic solution scans previously placed queens whenever it tests a new position.
For every attempted cell, it checks:
- The column above
- The upper-left diagonal
- The upper-right diagonal
Each validation may require:
O(n)
time.
We can reduce the safety check to:
O(1)
by storing which columns and diagonals are already occupied.
Approach 2 — HashSet-Based Backtracking
Core Idea
Maintain three sets:
Occupied columns
Occupied descending diagonals
Occupied ascending diagonals
For a position:
(row, column)
check whether its column or diagonal identifier already exists in the corresponding set.
Diagonal Formulas
Every cell on the same diagonal shares a common mathematical identifier.
Descending Diagonal
Cells running from upper-left to lower-right share:
row - column
Examples:
(0,0) → 0
(1,1) → 0
(2,2) → 0
(3,3) → 0
These cells lie on the same diagonal.
Ascending Diagonal
Cells running from upper-right to lower-left share:
row + column
Examples:
(0,3) → 3
(1,2) → 3
(2,1) → 3
(3,0) → 3
These cells also lie on the same diagonal.
Conflict Detection
A queen can be placed at:
(row, column)
only when all three checks are false:
columns.contains(column)
descendingDiagonals.contains(
row - column)
ascendingDiagonals.contains(
row + column)
If none are occupied, the position is safe.
Choose–Explore–Unchoose with Sets
Choose
columns.add(column);
descendingDiagonals.add(
row - column);
ascendingDiagonals.add(
row + column);
board[row][column] = 'Q';
Explore
backtrack(
row + 1,
board,
columns,
descendingDiagonals,
ascendingDiagonals,
result);
Unchoose
board[row][column] = '.';
columns.remove(column);
descendingDiagonals.remove(
row - column);
ascendingDiagonals.remove(
row + column);
Every state change made during the choose step must be reversed.
Java Code — HashSet Optimization
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class NQueensUsingSets {
public List<List<String>> solveNQueens(
int n) {
if (n <= 0) {
return List.of();
}
char[][] board =
new char[n][n];
for (char[] row : board) {
Arrays.fill(
row,
'.');
}
List<List<String>> result =
new ArrayList<>();
Set<Integer> columns =
new HashSet<>();
Set<Integer> descendingDiagonals =
new HashSet<>();
Set<Integer> ascendingDiagonals =
new HashSet<>();
backtrack(
0,
board,
columns,
descendingDiagonals,
ascendingDiagonals,
result);
return result;
}
private void backtrack(
int row,
char[][] board,
Set<Integer> columns,
Set<Integer> descendingDiagonals,
Set<Integer> ascendingDiagonals,
List<List<String>> result) {
if (row == board.length) {
result.add(
buildBoard(board));
return;
}
for (int column = 0;
column < board.length;
column++) {
int descending =
row - column;
int ascending =
row + column;
if (columns.contains(column)
|| descendingDiagonals
.contains(descending)
|| ascendingDiagonals
.contains(ascending)) {
continue;
}
board[row][column] = 'Q';
columns.add(column);
descendingDiagonals.add(
descending);
ascendingDiagonals.add(
ascending);
backtrack(
row + 1,
board,
columns,
descendingDiagonals,
ascendingDiagonals,
result);
board[row][column] = '.';
columns.remove(column);
descendingDiagonals.remove(
descending);
ascendingDiagonals.remove(
ascending);
}
}
private List<String> buildBoard(
char[][] board) {
List<String> configuration =
new ArrayList<>(
board.length);
for (char[] row : board) {
configuration.add(
new String(row));
}
return configuration;
}
}
HashSet Solution Complexity
HashSet lookup, insertion, and removal are:
O(1)
on average.
The search still explores a factorial-sized decision space, but every safety check is much faster than scanning the board.
| Complexity | Value |
|---|---|
| Search Time | Approximately O(n!) |
| Safety Check | O(1) average |
| Board Snapshot per Solution | O(n²) |
| Board Space | O(n²) |
| Set Space | O(n) |
| Recursion Stack | O(n) |
Approach 3 — Boolean Array Optimization
Why Use Boolean Arrays?
HashSets are readable and flexible, but N-Queens uses fixed integer ranges.
Boolean arrays provide:
- Constant-time lookup
- Lower allocation overhead
- Better cache locality
- No hashing cost
- Predictable memory usage
Maintain:
boolean[] columns;
boolean[] descendingDiagonals;
boolean[] ascendingDiagonals;
Column Array Size
There are:
n
columns.
Therefore:
boolean[] columns =
new boolean[n];
Diagonal Array Size
An n × n board has:
2n - 1
diagonals in each direction.
Therefore:
boolean[] descendingDiagonals =
new boolean[2 * n - 1];
boolean[] ascendingDiagonals =
new boolean[2 * n - 1];
Problem with row - column
The value:
row - column
can be negative.
For an n × n board, its range is:
-(n - 1) through n - 1
Array indexes cannot be negative.
Add an offset:
n - 1
Formula:
descending index
=
row - column + n - 1
Ascending Diagonal Index
The value:
row + column
is already non-negative.
Its range is:
0 through 2n - 2
Formula:
ascending index
=
row + column
Diagonal Index Example for n = 4
For:
row = 1
column = 3
Descending diagonal:
1 - 3 + 4 - 1
=
1
Ascending diagonal:
1 + 3
=
4
Optimized Java Solution
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NQueensOptimized {
public List<List<String>> solveNQueens(
int n) {
if (n <= 0) {
return List.of();
}
char[][] board =
new char[n][n];
for (char[] row : board) {
Arrays.fill(
row,
'.');
}
boolean[] columns =
new boolean[n];
boolean[] descendingDiagonals =
new boolean[2 * n - 1];
boolean[] ascendingDiagonals =
new boolean[2 * n - 1];
List<List<String>> result =
new ArrayList<>();
backtrack(
0,
board,
columns,
descendingDiagonals,
ascendingDiagonals,
result);
return result;
}
private void backtrack(
int row,
char[][] board,
boolean[] columns,
boolean[] descendingDiagonals,
boolean[] ascendingDiagonals,
List<List<String>> result) {
if (row == board.length) {
result.add(
buildBoard(board));
return;
}
int n = board.length;
for (int column = 0;
column < n;
column++) {
int descendingIndex =
row - column + n - 1;
int ascendingIndex =
row + column;
if (columns[column]
|| descendingDiagonals[
descendingIndex]
|| ascendingDiagonals[
ascendingIndex]) {
continue;
}
board[row][column] = 'Q';
columns[column] = true;
descendingDiagonals[
descendingIndex] = true;
ascendingDiagonals[
ascendingIndex] = true;
backtrack(
row + 1,
board,
columns,
descendingDiagonals,
ascendingDiagonals,
result);
board[row][column] = '.';
columns[column] = false;
descendingDiagonals[
descendingIndex] = false;
ascendingDiagonals[
ascendingIndex] = false;
}
}
private List<String> buildBoard(
char[][] board) {
List<String> result =
new ArrayList<>(
board.length);
for (char[] row : board) {
result.add(
new String(row));
}
return result;
}
}
Compact Optimized Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
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, '.');
}
boolean[] columns =
new boolean[n];
boolean[] diagonalOne =
new boolean[2 * n - 1];
boolean[] diagonalTwo =
new boolean[2 * n - 1];
solve(
0,
board,
columns,
diagonalOne,
diagonalTwo,
result);
return result;
}
private void solve(
int row,
char[][] board,
boolean[] columns,
boolean[] diagonalOne,
boolean[] diagonalTwo,
List<List<String>> result) {
int n = board.length;
if (row == n) {
List<String> solution =
new ArrayList<>(n);
for (char[] boardRow : board) {
solution.add(
new String(boardRow));
}
result.add(solution);
return;
}
for (int column = 0;
column < n;
column++) {
int firstDiagonal =
row - column + n - 1;
int secondDiagonal =
row + column;
if (columns[column]
|| diagonalOne[firstDiagonal]
|| diagonalTwo[secondDiagonal]) {
continue;
}
board[row][column] = 'Q';
columns[column] = true;
diagonalOne[firstDiagonal] = true;
diagonalTwo[secondDiagonal] = true;
solve(
row + 1,
board,
columns,
diagonalOne,
diagonalTwo,
result);
board[row][column] = '.';
columns[column] = false;
diagonalOne[firstDiagonal] = false;
diagonalTwo[secondDiagonal] = false;
}
}
}
Optimized Dry Run for n = 4
Suppose a queen is placed at:
row = 0
column = 1
Update:
columns[1] = true
Descending diagonal:
0 - 1 + 3 = 2
descendingDiagonals[2] = true
Ascending diagonal:
0 + 1 = 1
ascendingDiagonals[1] = true
When testing row 1, column 2:
descending index
=
1 - 2 + 3
=
2
Since:
descendingDiagonals[2] == true
the position is rejected immediately.
No board scanning is required.
Why Boolean Arrays Are Usually Best
| Board Scanning | HashSets | Boolean Arrays |
|---|---|---|
| O(n) safety check | O(1) average | O(1) |
| Simple visual logic | Clear formulas | Fastest common implementation |
| No extra conflict structures | Hashing overhead | Fixed memory |
| Easy for beginners | Good transition | Best interview optimization |
For most interviews, explain the board-scanning solution first and then optimize using boolean arrays.
Approach 4 — Store Only Queen Positions
The board is needed only when returning solutions.
During recursion, store:
int[] queenColumns
where:
queenColumns[row] = column
This reduces search-state memory.
Java Code — Positions and Boolean Arrays
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NQueensUsingPositions {
public List<List<String>> solveNQueens(
int n) {
if (n <= 0) {
return List.of();
}
int[] queenColumns =
new int[n];
Arrays.fill(
queenColumns,
-1);
boolean[] columns =
new boolean[n];
boolean[] descendingDiagonals =
new boolean[2 * n - 1];
boolean[] ascendingDiagonals =
new boolean[2 * n - 1];
List<List<String>> result =
new ArrayList<>();
backtrack(
0,
queenColumns,
columns,
descendingDiagonals,
ascendingDiagonals,
result);
return result;
}
private void backtrack(
int row,
int[] queenColumns,
boolean[] columns,
boolean[] descendingDiagonals,
boolean[] ascendingDiagonals,
List<List<String>> result) {
int n = queenColumns.length;
if (row == n) {
result.add(
buildBoard(
queenColumns));
return;
}
for (int column = 0;
column < n;
column++) {
int descending =
row - column + n - 1;
int ascending =
row + column;
if (columns[column]
|| descendingDiagonals[
descending]
|| ascendingDiagonals[
ascending]) {
continue;
}
queenColumns[row] = column;
columns[column] = true;
descendingDiagonals[
descending] = true;
ascendingDiagonals[
ascending] = true;
backtrack(
row + 1,
queenColumns,
columns,
descendingDiagonals,
ascendingDiagonals,
result);
queenColumns[row] = -1;
columns[column] = false;
descendingDiagonals[
descending] = false;
ascendingDiagonals[
ascending] = false;
}
}
private List<String> buildBoard(
int[] queenColumns) {
int n = queenColumns.length;
List<String> board =
new ArrayList<>(n);
for (int row = 0;
row < n;
row++) {
char[] line =
new char[n];
Arrays.fill(
line,
'.');
line[queenColumns[row]] =
'Q';
board.add(
new String(line));
}
return board;
}
}
Search-State Space
Using positions and boolean arrays:
| State | Space |
|---|---|
| Queen positions | O(n) |
| Columns | O(n) |
| Two diagonal arrays | O(n) |
| Recursion stack | O(n) |
| Total auxiliary search state | O(n) |
The returned output still requires:
O(S × n²)
where S is the number of solutions.
Approach 5 — Bitmask Backtracking
Core Idea
For moderate board sizes, occupied columns and diagonals can be represented using bits.
A bit value of:
1
means the position is occupied or attacked.
A bit value of:
0
means the column is available.
Bitmasking provides:
- Very fast conflict checks
- Compact state
- Efficient solution counting
- Natural branch extraction
Bitmask State
Maintain three bitmasks:
columns
leftDiagonals
rightDiagonals
Each bit represents a column in the current row.
Full Mask
For an n × n board:
long fullMask =
(1L << n) - 1L;
For:
n = 4
1L << 4 = 10000₂
Subtract 1
1111₂
The four low bits represent the four board columns.
Available Positions
Calculate:
long available =
fullMask
& ~(columns
| leftDiagonals
| rightDiagonals);
This keeps only columns that are not attacked.
Extract the Lowest Available Position
long position =
available & -available;
This isolates the lowest set bit.
Example:
available = 10100₂
position = 00100₂
Remove the Selected Position
available -= position;
or:
available &= available - 1;
Both remove the lowest set bit.
Update Diagonals for the Next Row
After selecting a position:
(columns | position)
marks the selected column.
Diagonal attacks shift when moving to the next row.
(leftDiagonals | position) << 1
(rightDiagonals | position) >> 1
Bitmask Count-Only Solution
public class NQueensBitmaskCounter {
public long totalNQueens(
int n) {
if (n <= 0 || n > 63) {
throw new IllegalArgumentException(
"Require 1 <= n <= 63");
}
long fullMask =
(1L << n) - 1L;
return count(
fullMask,
0L,
0L,
0L);
}
private long count(
long fullMask,
long columns,
long leftDiagonals,
long rightDiagonals) {
if (columns == fullMask) {
return 1L;
}
long available =
fullMask
& ~(columns
| leftDiagonals
| rightDiagonals);
long solutions = 0L;
while (available != 0L) {
long position =
available
& -available;
available -= position;
solutions += count(
fullMask,
columns | position,
(leftDiagonals
| position) << 1,
(rightDiagonals
| position) >>> 1);
}
return solutions;
}
}
Important Bit-Shift Detail
Use unsigned right shift:
>>>
instead of signed right shift:
>>
for predictable zero-filling behavior.
The full mask removes bits outside the active board width during availability calculation.
Bitmask Solution Limitation
This expression:
1L << n
has limitations for n = 64.
For practical interview use, bitmask N-Queens usually targets much smaller values.
A simpler validation may restrict:
1 <= n <= 32
or another reasonable range.
Bitmask Solution That Returns Boards
To build actual boards, track the selected bit for each row.
Java Code — Bitmask Board Generation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NQueensBitmask {
public List<List<String>> solveNQueens(
int n) {
if (n <= 0 || n > 32) {
throw new IllegalArgumentException(
"Require 1 <= n <= 32");
}
long fullMask =
(1L << n) - 1L;
int[] queenColumns =
new int[n];
Arrays.fill(
queenColumns,
-1);
List<List<String>> result =
new ArrayList<>();
backtrack(
0,
n,
fullMask,
0L,
0L,
0L,
queenColumns,
result);
return result;
}
private void backtrack(
int row,
int n,
long fullMask,
long columns,
long leftDiagonals,
long rightDiagonals,
int[] queenColumns,
List<List<String>> result) {
if (row == n) {
result.add(
buildBoard(
queenColumns));
return;
}
long available =
fullMask
& ~(columns
| leftDiagonals
| rightDiagonals);
while (available != 0L) {
long position =
available
& -available;
available -= position;
int column =
Long.numberOfTrailingZeros(
position);
queenColumns[row] =
column;
backtrack(
row + 1,
n,
fullMask,
columns | position,
(leftDiagonals
| position) << 1,
(rightDiagonals
| position) >>> 1,
queenColumns,
result);
queenColumns[row] = -1;
}
}
private List<String> buildBoard(
int[] queenColumns) {
int n = queenColumns.length;
List<String> board =
new ArrayList<>(n);
for (int row = 0;
row < n;
row++) {
char[] line =
new char[n];
Arrays.fill(
line,
'.');
line[queenColumns[row]] =
'Q';
board.add(
new String(line));
}
return board;
}
}
Bitmask Dry Run for n = 4
Initial:
fullMask = 1111
columns = 0000
leftDiagonals = 0000
rightDiagonals = 0000
Available:
1111
Choose column 1:
position = 0010
Next row:
columns = 0010
Left diagonal attacks:
0010 << 1
=
0100
Right diagonal attacks:
0010 >>> 1
=
0001
Unavailable:
0010 | 0100 | 0001
=
0111
Available columns:
1111 & ~0111
=
1000
Only column 3 is available in the next row.
This matches the first valid n = 4 solution path.
Bitmask Advantages and Trade-Offs
| Advantages | Trade-Offs |
|---|---|
| Very fast operations | Harder to understand |
| Compact state | Easy to make shift errors |
| Excellent for counting | Limited by integer bit width |
| Avoids arrays and sets | Less suitable as first explanation |
| Good for optimization discussions | Board construction still costs O(n²) |
Use boolean arrays for clarity and bitmasks for advanced optimization.
N-Queens II — Count Solutions
LeetCode #52 asks only for the number of valid arrangements.
Since boards do not need to be constructed, the algorithm can avoid:
char[][]- Strings
- Result lists
- Board snapshots
Count Using Boolean Arrays
public class NQueensCounter {
public int totalNQueens(
int n) {
if (n <= 0) {
return 0;
}
boolean[] columns =
new boolean[n];
boolean[] descendingDiagonals =
new boolean[2 * n - 1];
boolean[] ascendingDiagonals =
new boolean[2 * n - 1];
return count(
0,
n,
columns,
descendingDiagonals,
ascendingDiagonals);
}
private int count(
int row,
int n,
boolean[] columns,
boolean[] descendingDiagonals,
boolean[] ascendingDiagonals) {
if (row == n) {
return 1;
}
int solutions = 0;
for (int column = 0;
column < n;
column++) {
int descending =
row - column + n - 1;
int ascending =
row + column;
if (columns[column]
|| descendingDiagonals[
descending]
|| ascendingDiagonals[
ascending]) {
continue;
}
columns[column] = true;
descendingDiagonals[
descending] = true;
ascendingDiagonals[
ascending] = true;
solutions += count(
row + 1,
n,
columns,
descendingDiagonals,
ascendingDiagonals);
columns[column] = false;
descendingDiagonals[
descending] = false;
ascendingDiagonals[
ascending] = false;
}
return solutions;
}
}
Known Small Solution Counts
Useful validation values include:
| n | Number of Solutions |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 2 |
| 5 | 10 |
| 6 | 4 |
| 7 | 40 |
| 8 | 92 |
These counts are useful for unit testing.
Return Only One Solution
Sometimes the requirement is to find any valid arrangement.
Return a boolean to stop after the first solution.
Java Code — Find One Board
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FindOneNQueensSolution {
public List<String> solve(
int n) {
if (n <= 0) {
return List.of();
}
int[] queenColumns =
new int[n];
Arrays.fill(
queenColumns,
-1);
boolean[] columns =
new boolean[n];
boolean[] descendingDiagonals =
new boolean[2 * n - 1];
boolean[] ascendingDiagonals =
new boolean[2 * n - 1];
boolean found =
backtrack(
0,
queenColumns,
columns,
descendingDiagonals,
ascendingDiagonals);
return found
? buildBoard(queenColumns)
: List.of();
}
private boolean backtrack(
int row,
int[] queenColumns,
boolean[] columns,
boolean[] descendingDiagonals,
boolean[] ascendingDiagonals) {
int n = queenColumns.length;
if (row == n) {
return true;
}
for (int column = 0;
column < n;
column++) {
int descending =
row - column + n - 1;
int ascending =
row + column;
if (columns[column]
|| descendingDiagonals[
descending]
|| ascendingDiagonals[
ascending]) {
continue;
}
queenColumns[row] =
column;
columns[column] = true;
descendingDiagonals[
descending] = true;
ascendingDiagonals[
ascending] = true;
if (backtrack(
row + 1,
queenColumns,
columns,
descendingDiagonals,
ascendingDiagonals)) {
return true;
}
queenColumns[row] =
-1;
columns[column] = false;
descendingDiagonals[
descending] = false;
ascendingDiagonals[
ascending] = false;
}
return false;
}
private List<String> buildBoard(
int[] queenColumns) {
int n = queenColumns.length;
List<String> board =
new ArrayList<>(n);
for (int row = 0;
row < n;
row++) {
char[] line =
new char[n];
Arrays.fill(
line,
'.');
line[queenColumns[row]] =
'Q';
board.add(
new String(line));
}
return board;
}
}
Why Early Exit Helps
When only one solution is required, continuing after finding one board wastes work.
The boolean result propagates success through the recursion stack.
graph TD
Solution_Found["Solution Found"] --> Return_true["Return true"]
Return_true["Return true"] --> Skip_remaining_branches["Skip remaining branches"]
Skip_remaining_branches["Skip remaining branches"] --> Return_result["Return result"]
Symmetry Optimization
N-Queens boards are symmetric.
A solution with the first queen in a left-side column often has a mirrored solution with the first queen in the corresponding right-side column.
For count-only problems:
- Search only half of the first-row columns.
- Double the count.
- For odd
n, process the middle column separately.
Symmetry Example
For:
n = 4
First-row column 1 produces:
.Q..
...Q
Q...
..Q.
Its horizontal mirror begins with column 2:
..Q.
Q...
...Q
.Q..
Symmetry-Optimized Count
public class NQueensSymmetryCounter {
public long totalNQueens(
int n) {
if (n <= 0 || n > 63) {
throw new IllegalArgumentException(
"Require 1 <= n <= 63");
}
long fullMask =
(1L << n) - 1L;
int half =
n / 2;
long total = 0L;
for (int column = 0;
column < half;
column++) {
long position =
1L << column;
total += count(
fullMask,
position,
position << 1,
position >>> 1);
}
total *= 2L;
if (n % 2 == 1) {
long middlePosition =
1L << half;
total += count(
fullMask,
middlePosition,
middlePosition << 1,
middlePosition >>> 1);
}
return total;
}
private long count(
long fullMask,
long columns,
long leftDiagonals,
long rightDiagonals) {
if (columns == fullMask) {
return 1L;
}
long available =
fullMask
& ~(columns
| leftDiagonals
| rightDiagonals);
long total = 0L;
while (available != 0L) {
long position =
available
& -available;
available -= position;
total += count(
fullMask,
columns | position,
(leftDiagonals
| position) << 1,
(rightDiagonals
| position) >>> 1);
}
return total;
}
}
Symmetry Optimization Limitation
Doubling mirrored branches works naturally for counting.
When returning all boards:
- Mirrored boards must be constructed.
- Rotation and reflection uniqueness may matter.
- The implementation becomes more complicated.
- LeetCode #51 expects all distinct placements, including mirrored solutions.
Use symmetry primarily for count-only optimization.
Fundamental Solutions
Some mathematical variants count boards as equivalent under:
- Rotation
- Reflection
These are called fundamental solutions.
LeetCode treats transformed boards as distinct when their queen placements differ.
For example, mirrored 4 × 4 boards are returned as two solutions.
Parallelizing N-Queens
Top-level first-row branches are independent.
A branch beginning with:
row 0, column 0
does not share recursive state with a branch beginning with:
row 0, column 1
This makes top-level parallelization possible.
Parallelization Strategy
- Create one task for each valid first-row column.
- Give each task independent state.
- Execute tasks in a bounded thread pool.
- Combine counts or results.
Never share mutable arrays across concurrent branches without copying them.
Parallel Count Example
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
public class ParallelNQueensCounter {
private final ForkJoinPool pool;
public ParallelNQueensCounter(
int parallelism) {
if (parallelism <= 0) {
throw new IllegalArgumentException(
"Parallelism must be positive");
}
this.pool =
new ForkJoinPool(
parallelism);
}
public long totalNQueens(
int n) {
if (n <= 0 || n > 32) {
throw new IllegalArgumentException(
"Require 1 <= n <= 32");
}
long fullMask =
(1L << n) - 1L;
List<Future<Long>> futures =
new ArrayList<>();
for (int column = 0;
column < n;
column++) {
long position =
1L << column;
futures.add(
pool.submit(
() -> count(
fullMask,
position,
position << 1,
position >>> 1)));
}
long total = 0L;
for (Future<Long> future : futures) {
try {
total += future.get();
} catch (Exception exception) {
throw new IllegalStateException(
"N-Queens task failed",
exception);
}
}
return total;
}
private long count(
long fullMask,
long columns,
long leftDiagonals,
long rightDiagonals) {
if (columns == fullMask) {
return 1L;
}
long available =
fullMask
& ~(columns
| leftDiagonals
| rightDiagonals);
long total = 0L;
while (available != 0L) {
long position =
available
& -available;
available -= position;
total += count(
fullMask,
columns | position,
(leftDiagonals
| position) << 1,
(rightDiagonals
| position) >>> 1);
}
return total;
}
public void close() {
pool.shutdown();
}
}
Parallelization Trade-Offs
Parallel processing may help for larger n, but:
- Small boards complete too quickly.
- Thread scheduling adds overhead.
- Branch workloads are uneven.
- Returning boards creates expensive result merging.
- Unbounded recursive task creation is dangerous.
- CPU and memory usage can increase sharply.
Parallelize only coarse top-level branches.
Advanced Complexity Discussion
N-Queens is commonly described as:
O(n!)
because each row selects a unique column.
However, this is an upper-bound simplification.
The actual number of explored nodes depends on:
- Diagonal pruning
- Column order
- Board size
- Symmetry optimizations
- Whether all solutions or one solution are required
Cost Components
Search
Approximately factorial:
O(n!)
Safety Check
- Board scanning:
O(n) - HashSets:
O(1)average - Boolean arrays:
O(1) - Bitmasks:
O(1)
Board Construction
For every solution:
O(n²)
Output-Sensitive Complexity
If there are S solutions:
Output cost
=
O(S × n²)
Even a highly optimized search must pay this cost when every board is returned.
Auxiliary Space by Approach
| Approach | Auxiliary Search Space |
|---|---|
char[][] + scanning |
O(n²) |
char[][] + sets |
O(n²) |
| Positions + boolean arrays | O(n) |
| Bitmask count-only | O(n) recursion stack |
| Bitmask iterative possibilities | Potentially lower stack with manual stack |
Heuristic Column Ordering
For standard N-Queens, trying columns from left to right is sufficient.
In general constraint satisfaction problems, variable and value ordering can dramatically affect runtime.
Common heuristics include:
- Most constrained variable first
- Least constraining value
- Center columns first
- Symmetry-aware ordering
- Domain-size ordering
Center-First Column Order
For some board sizes, trying center columns first may find one solution sooner.
Example order for n = 7:
3, 2, 4, 1, 5, 0, 6
This does not change worst-case complexity.
It may help only when:
- One solution is required.
- Search order affects early success.
It does not necessarily reduce work when all solutions must be returned.
Production Trade-Offs
N-Queens illustrates several production engineering decisions.
Readability vs Performance
- Board scanning is easiest to explain.
- Boolean arrays provide excellent balance.
- Bitmasks maximize speed but reduce readability.
Returning Results vs Counting
Returning boards requires substantial memory.
Counting solutions avoids:
- Board allocation
- String construction
- Result retention
Input Size Limits
Because runtime grows rapidly, production APIs should enforce safe limits.
Example:
if (n > 14) {
throw new IllegalArgumentException(
"Board size exceeds supported limit");
}
The actual limit depends on:
- Hardware
- Algorithm
- Timeout requirements
- Whether boards are returned or counted
Cancellation and Timeouts
Long-running searches should support cancellation.
Possible techniques:
- Thread interruption
- Deadline checks
- Maximum-node limits
- Request cancellation tokens
- Bounded executor timeouts
Deadline-Aware Search Example
public class SearchDeadline {
private final long deadlineNanos;
public SearchDeadline(
long timeoutMillis) {
this.deadlineNanos =
System.nanoTime()
+ timeoutMillis
* 1_000_000L;
}
public void check() {
if (System.nanoTime()
>= deadlineNanos) {
throw new IllegalStateException(
"Search deadline exceeded");
}
}
}
Call the deadline check periodically during recursion.
Avoid checking on every tiny operation if the overhead becomes significant.
Real-World Pattern — Constraint Satisfaction
N-Queens models a broader category of problems.
Variables
Rows
Values
Columns
Constraints
No equal columns
No equal diagonals
This same structure appears in:
- Employee scheduling
- Timetable generation
- Register allocation
- Graph coloring
- Resource placement
- Puzzle solving
- Assignment planning
N-Queens vs Sudoku
| N-Queens | Sudoku |
|---|---|
| One queen per row | Fill many empty cells |
| Column and diagonal constraints | Row, column, and box constraints |
| Candidate values are columns | Candidate values are digits |
Depth is n rows |
Depth can be number of empty cells |
| Simple fixed structure | More complex domain constraints |
Both use:
Choose
Validate
Explore
Unchoose
N-Queens vs Graph Coloring
N-Queens can be viewed as placing values under pairwise constraints.
Graph coloring similarly assigns colors to vertices while ensuring adjacent vertices differ.
Both problems:
- Are constraint satisfaction problems
- Benefit from early validation
- Have exponential worst-case behavior
- Can use heuristics and pruning
- May be solved with specialized solvers
Common Optimization Mistakes
Mistake 1 — Incorrect Diagonal Array Size
Correct:
2 * n - 1
There are 2n - 1 diagonals in each direction.
Mistake 2 — Forgetting the Descending Offset
Incorrect:
descending[row - column]
This may use a negative index.
Correct:
row - column + n - 1
Mistake 3 — Mixing Diagonal Formulas
Use:
row - column + n - 1
for one direction and:
row + column
for the other.
Mistake 4 — Not Clearing Conflict Arrays
Every true value set during placement must be restored to false after recursion.
Mistake 5 — Sharing Mutable State Between Parallel Tasks
Each task must have isolated state.
Mistake 6 — Applying Symmetry Doubling Incorrectly
For odd n, the middle first-row column does not have a distinct mirror branch and must be counted separately.
Mistake 7 — Using Int Bitmasks for Large n
An int has only 32 bits.
Use long for wider masks, and enforce an explicit limit.
Mistake 8 — Constructing Boards for Count-Only Problems
Avoid board creation when only the number of solutions is needed.
Senior-Level Interview Questions
Why Does row - column Identify a Diagonal?
Moving one step down and one step right increases both row and column by one.
Therefore:
(row + 1) - (column + 1)
=
row - column
The difference remains constant.
Why Does row + column Identify the Other Diagonal?
Moving one step down and one step left changes:
row + 1
column - 1
Therefore:
(row + 1) + (column - 1)
=
row + column
The sum remains constant.
Why Is One Queen per Row Sufficient?
A valid solution has n queens on n rows.
Since queens cannot share rows, each row must contain exactly one queen.
This lets the recursive depth represent the current row.
Why Is the Search Approximately O(n!)?
Each row must select a column not used by previous rows.
Ignoring diagonal constraints:
n × (n - 1) × ... × 1
=
n!
Diagonal pruning reduces the actual number of explored branches.
Can Dynamic Programming Solve N-Queens Efficiently?
Standard N-Queens does not have the same overlapping subproblem structure as classic dynamic programming problems.
A state can be represented by masks, and memoization may count equivalent remaining configurations in some formulations.
However:
- Row is often implied by the number of selected columns.
- Diagonal masks differ heavily across branches.
- The state space remains large.
- Plain backtracking with bitmasks is typically preferred.
Can Constraint Propagation Improve It?
Yes.
Advanced solvers may:
- Track candidate domains
- Choose the most constrained row
- Propagate attacks
- Use exact cover
- Apply SAT or CSP techniques
The standard row-by-row approach already performs basic forward constraint checking.
How Would Exact Cover Solve N-Queens?
N-Queens can be transformed into an exact-cover-like formulation using:
- Row constraints
- Column constraints
- Diagonal constraints
Algorithms such as Dancing Links may be used for related constraint problems.
For interviews, backtracking is more appropriate unless exact cover is specifically requested.
How Would You Benchmark the Approaches?
Use JMH and compare:
- Board scanning
- HashSets
- Boolean arrays
- Bitmask recursion
- Symmetry-optimized bitmask counting
Measure:
- Runtime
- Allocation rate
- GC pressure
- Number of visited nodes
- Scaling by board size
Avoid using one execution with System.currentTimeMillis().
Strong Senior-Level Explanation
I model each row as a variable whose value is the queen’s column. Because exactly one queen is placed per row, the recursive depth is the current row. To validate a candidate in constant time, I track occupied columns,
row - columndiagonals, androw + columndiagonals. For array indexing, I offsetrow - columnbyn - 1. I mark these structures before recursion and restore them afterward. The search is approximately factorial, while each conflict check is O(1). If only the count is required, I avoid constructing boards and can further optimize with bitmasks and first-row symmetry.
Additional Unit Tests — Optimized Solution
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.Test;
class NQueensOptimizedTest {
private final NQueensOptimized solution =
new NQueensOptimized();
@Test
void shouldReturnCorrectCountsForSmallBoards() {
assertEquals(
1,
solution.solveNQueens(1)
.size());
assertEquals(
0,
solution.solveNQueens(2)
.size());
assertEquals(
0,
solution.solveNQueens(3)
.size());
assertEquals(
2,
solution.solveNQueens(4)
.size());
assertEquals(
10,
solution.solveNQueens(5)
.size());
}
@Test
void everyRowShouldContainOneQueen() {
List<List<String>> boards =
solution.solveNQueens(6);
for (List<String> board : boards) {
for (String row : board) {
long queenCount =
row.chars()
.filter(
character ->
character == 'Q')
.count();
assertEquals(
1L,
queenCount);
}
}
}
@Test
void shouldReturnEmptyForInvalidSize() {
assertTrue(
solution.solveNQueens(0)
.isEmpty());
}
}
Unit Tests — Count-Only Solution
import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.api.Test;
class NQueensCounterTest {
private final NQueensCounter solution =
new NQueensCounter();
@Test
void shouldCountKnownSolutions() {
assertEquals(
1,
solution.totalNQueens(1));
assertEquals(
0,
solution.totalNQueens(2));
assertEquals(
0,
solution.totalNQueens(3));
assertEquals(
2,
solution.totalNQueens(4));
assertEquals(
10,
solution.totalNQueens(5));
assertEquals(
4,
solution.totalNQueens(6));
assertEquals(
40,
solution.totalNQueens(7));
assertEquals(
92,
solution.totalNQueens(8));
}
}
Unit Tests — Bitmask Counter
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;
import org.junit.jupiter.api.Test;
class NQueensBitmaskCounterTest {
private final NQueensBitmaskCounter solution =
new NQueensBitmaskCounter();
@Test
void shouldCountEightQueensSolutions() {
assertEquals(
92L,
solution.totalNQueens(8));
}
@Test
void shouldCountOneQueenSolution() {
assertEquals(
1L,
solution.totalNQueens(1));
}
@Test
void shouldRejectInvalidSize() {
assertThrows(
IllegalArgumentException.class,
() -> solution.totalNQueens(0));
}
}
Unit Test — Find One Solution
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import java.util.List;
import org.junit.jupiter.api.Test;
class FindOneNQueensSolutionTest {
private final FindOneNQueensSolution solution =
new FindOneNQueensSolution();
@Test
void shouldReturnOneValidBoard() {
List<String> board =
solution.solve(8);
assertFalse(
board.isEmpty());
assertEquals(
8,
board.size());
for (String row : board) {
assertEquals(
1L,
row.chars()
.filter(
character ->
character == 'Q')
.count());
}
}
@Test
void shouldReturnEmptyWhenNoSolutionExists() {
assertEquals(
List.of(),
solution.solve(3));
}
}
Approach Comparison
| Approach | Safety Check | Auxiliary Search Space | Main Benefit |
|---|---|---|---|
| Board scanning | O(n) | O(n²) | Easiest to understand |
| Position array scanning | O(n) | O(n) | Lower search-state memory |
| HashSets | O(1) average | O(n²) with board | Clear diagonal formulas |
| Boolean arrays | O(1) | O(n) or O(n²) | Best clarity/performance balance |
| Bitmasks | O(1) | O(n) stack | Fastest compact state |
| Symmetry + bitmask | O(1) | O(n) stack | Strong count-only optimization |
Final Summary
N-Queens is a classic constraint-satisfaction problem solved effectively with backtracking.
The basic algorithm processes one row at a time:
graph TD
Try_Column["Try Column"] --> Check_Constraints["Check Constraints"]
Check_Constraints["Check Constraints"] --> Place_Queen["Place Queen"]
Place_Queen["Place Queen"] --> Recurse["Recurse"]
Recurse["Recurse"] --> Remove_Queen["Remove Queen"]
The first implementation scans the board to detect conflicts.
The optimized implementation tracks:
Column
row - column diagonal
row + column diagonal
This reduces each safety check to constant time.
Boolean arrays provide the best balance of readability and performance.
Bitmasks provide a compact, high-performance alternative, especially for count-only variants.
For count-only problems, avoid constructing boards.
For advanced optimization, use first-row symmetry and coarse-grained parallel branches.
Key Takeaways
- Place exactly one queen per row.
- The recursive depth represents the current row.
- Try every column in that row.
- Reject occupied columns and diagonals.
row - columnidentifies one diagonal direction.row + columnidentifies the other direction.- Add
n - 1to the difference for array indexing. - Boolean arrays provide O(1) conflict checks.
- Mark conflict state before recursion.
- Restore every state change after recursion.
- Save a board only after all rows are complete.
- Use an
int[]position array to reduce search-state memory. - Construct boards only when a complete solution is found.
- Use bitmasks for advanced performance optimization.
- Use unsigned right shifts for bitmask diagonal movement.
- Count-only solutions should avoid board allocation.
- Return a boolean to stop after finding one solution.
- Symmetry can nearly halve first-row count searches.
- Parallelize only independent top-level branches.
- The search remains approximately factorial.
- Output construction requires O(n²) per board.
- N-Queens demonstrates patterns used in scheduling, placement, graph coloring, and constraint solvers.
N-Queens Interview Checklist
Before an interview, be prepared to explain:
- Why one queen is placed per row
- The choose–explore–unchoose process
- Column conflict tracking
- Both diagonal formulas
- The diagonal offset
- The base condition
- Board conversion
- Basic and optimized complexity
- Boolean arrays vs HashSets
- Bitmask representation
- N-Queens II
- Early exit for one solution
- Symmetry pruning
- Parallelization trade-offs
- Real-world constraint-satisfaction applications