N-Queens
- 21 hours ago
- 8 min read
Managing Constraints While Exploring Possibilities
Interviewers love the N-Queens problem because it reveals whether you can reason about constraints and prune aggressively, or whether you reach for brute force and hope for the best. If you've been building your backtracking intuition through Subsets, Combination Sum, and Letter Combinations, the skeleton here will feel familiar. What's new is the constraint tracking. That's where this problem gets interesting.
Problem Statement
Given an integer n, return all distinct solutions to the n-queens puzzle.
Place n queens on an n × n chessboard such that no two queens attack each other. Queens attack along rows, columns, and diagonals.
Return all valid board configurations. Each configuration is represented as a list of strings, where 'Q' marks a queen and '.' marks an empty cell.
Example - n = 4:
[".Q..","...Q","Q...","..Q."]
["..Q.","Q...","...Q",".Q.."]1. Clarify Requirements Before Jumping Into Code
Before touching code, restate the constraints clearly.
Input: Integer n.
Output: All valid board configurations where n queens are placed with no two attacking each other.
Attack conditions: Two queens attack if they share a row, column, or diagonal.
Key observation to state out loud: We need exactly one queen per row. That's not given explicitly in the problem, but it follows immediately from the constraints. If any row has zero queens, some other row must have two, which would be an attack. So each row gets exactly one queen. This single observation transforms the problem from "place n queens anywhere" into "for each row, choose which column."
Edge cases worth naming:
n = 1: One queen on a 1×1 board. Always valid.
n = 2 or n = 3: No valid solutions exist.
n = 4: Two solutions.
2. Identify the Category of the Problem
This is backtracking, but with a heavier emphasis on constraint propagation than any problem we've seen so far.
In Letter Combinations, there were no constraints between levels. Each digit's choices were completely independent. In Combination Sum, the only constraint was the running sum. Here, placing a queen in row i constrains which columns are available in every subsequent row. The choices at each level depend heavily on what was chosen before.
That's what makes N-Queens a genuine constraint satisfaction problem. The backtracking skeleton is the same. The interesting engineering is in how efficiently you check and track constraints.
3. Start With Brute Force to Build Intuition
The naive approach is to try placing queens on every square of the board in every combination of n squares, then check which configurations are valid.
How many configurations are there? You're choosing n squares from n² total - that's C(n², n). For n = 8, that's C(64, 8) = 4,426,165,368. For most of those, the queens obviously attack each other. Checking all of them is completely infeasible.
But the brute force reveals something useful: valid solutions are astronomically rare. For n = 8, there are only 92 valid configurations out of over 4 billion possibilities. That means the overwhelming majority of paths in our search tree are dead ends, which means aggressive pruning isn't just helpful, it's essential.
4. Brainstorm More Solutions
Step 1: Reframe the Problem
The brute force fails because we're treating the board as a 2D grid of independent squares. But we established that each row gets exactly one queen. So instead of asking "which squares do we place queens on?" we can ask the simpler question: "for each row, which column does the queen go in?"
This reframes N-Queens as a sequence of n decisions, one per row. At each step, we choose a column for the current row's queen. This is similar in structure to Letter Combinations - except instead of a phone map telling us which letters are valid, we have constraint checks telling us which columns are valid.
The recursion becomes: process rows 0 through n-1 in order, and at each row, try every column that doesn't conflict with any previously placed queen.
Step 2: Track Columns
The column constraint is straightforward: no two queens can share a column. We keep a set of columns that are already occupied. Before placing a queen at (row, col), check if col is in the set. If it is, skip. If not, add it, recurse, and remove it afterward.
Step 3: Track Diagonals
The diagonal constraint is trickier. For each new placement, you could always scan all previous queens to check whether they're on the same diagonal. That works, but it's O(n) per check. Can we do better?
Let's think about what it means for two queens to share a diagonal. If queen A is at (r1, c1) and queen B is at (r2, c2), they're on the same diagonal if moving from one to the other is an equal number of steps horizontally and vertically. In other words:
|r2 - r1| == |c2 - c1|Leaving the arithmetic to you, we can rearrange the terms in this equation to get something like r1-c1 == r2-c2, or r1+c1 = r2+c2.
What does that mean in terms of our grid? It means that every cell on the same diagonal will have either the same row - col value or the same row + col value.
Try it. Pick any main diagonal (top-left to bottom-right) and compute (row - col) for a few cells on it:
(0, 0) → 0 - 0 = 0
(1, 1) → 1 - 1 = 0
(2, 2) → 2 - 2 = 0
(3, 3) → 3 - 3 = 0Now try a neighboring diagonal:
(0, 1) → 0 - 1 = -1
(1, 2) → 1 - 2 = -1
(2, 3) → 2 - 3 = -1Every cell on the same main diagonal has the same row - col value. That's exactly the property we need - it means we can represent an entire diagonal as a single integer, check membership in O(1) with a set, and never scan previous queens at all.
We can use the addition version of the equation, r1+c1 = r2+c2, to see that the same is true for anti-diagonals (top-right to bottom-left). Every cell on the same anti-diagonal shares the same value of row + col. (0,2) gives 0+2=2. (1,1) gives 1+1=2. (2,0) gives 2+0=2.
So that means we need two sets - one for row - col values (main diagonals) and one for row + col values (anti-diagonals). Before placing a queen at (row, col), we check for diagonal collisions against both sets. We add to both sets after we place a queen, and we remove from both sets after we backtrack.
Let's verify with an example. Suppose we've placed a queen at (0, 1) in a 4×4 board. That queen attacks:
Column 1 (the entire second column)
Main diagonal where row - col = 0 - 1 = -1: cells (1,2), (2,3)
Anti-diagonal where row + col = 0 + 1 = 1: cells (1,0)
So in the next row, columns 0, 1, and 2 are all forbidden: 0 because of the anti-diagonal, 1 because of the column, and 2 because of the main diagonal. Only column 3 is available.
This O(1) diagonal check, using just arithmetic on coordinates, is far more efficient than scanning the board for attacks every time.
Step 4: How Much Does Pruning Help?
Our brute-force solution have a time complexity of O(n²choose n). This final solution gives us a time complexity of O(n!). Why? The O(n!) bound comes from the column constraint alone: the first row has n choices, the second has at most n-1 (one column is taken), the third at most n-2, and so on. Diagonal constraints prune further, so the actual number of nodes visited is much less than n! in practice.
5. Trade-Offs at a Glance
Approach | Time | Space | Notes |
Brute force (all placements) | O(n²choose n) | Large | Completely infeasible |
Backtracking + constraint sets | O(n!) | O(n) | Standard solution |
6. Pseudocode
result = empty list
cols = empty set
diag1 = empty set ← tracks row - col values
diag2 = empty set ← tracks row + col values
backtrack(row):
if row == n:
convert board to list of strings and add to result
return
for col from 0 to n-1:
if col ∈ cols OR (row-col) ∈ diag1 OR (row+col) ∈ diag2:
continue ← this placement is invalid
place queen: board[row][col] = 'Q'
add col to cols, (row-col) to diag1, (row+col) to diag2
backtrack(row + 1)
remove queen: board[row][col] = '.'
remove col from cols, (row-col) from diag1, (row+col) from diag2
call backtrack(0)
7. Edge Cases
n = 1: One queen on a 1×1 board. The loop places it at (0,0), recurses to row 1, and immediately records a solution. Output: [["Q"]].
n = 2 or n = 3: No valid solutions. The algorithm explores all possibilities and records nothing. Output: [].
n = 4: Two solutions. Good case to trace manually.
n = 8: 92 solutions. Don't trace by hand - just verify the count.
8. Full Solution
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class NQueens {
public static List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) java.util.Arrays.fill(row, '.');
backtrack(0, n, board, new HashSet<>(), new HashSet<>(), new HashSet<>(), result);
return result;
}
private static void backtrack(int row, int n, char[][] board,
Set<Integer> cols,
Set<Integer> diag1,
Set<Integer> diag2,
List<List<String>> result) {
if (row == n) {
List<String> solution = new ArrayList<>();
for (char[] r : board) solution.add(new String(r));
result.add(solution);
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) ||
diag1.contains(row - col) ||
diag2.contains(row + col)) {
continue;
}
board[row][col] = 'Q'; // choose
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
backtrack(row + 1, n, board, cols, diag1, diag2, result); // explore
board[row][col] = '.'; // un-choose
cols.remove(col);
diag1.remove(row - col);
diag2.remove(row + col);
}
}
}
Notice the symmetry: every line that adds to a set or places a queen before the recursive call has a mirror line that removes it afterward. Six lines of modification, six lines of restoration. That symmetry is a good sanity check - if your add/remove pairs don't match, you have a bug.
9. Test Your Solution
System.out.println(solveNQueens(1).size()); // 1
System.out.println(solveNQueens(2).size()); // 0
System.out.println(solveNQueens(3).size()); // 0
System.out.println(solveNQueens(4).size()); // 2
System.out.println(solveNQueens(5).size()); // 10
System.out.println(solveNQueens(8).size()); // 92
// Inspect the actual boards for n=4:
for (List<String> solution : solveNQueens(4)) {
for (String row : solution) System.out.println(row);
System.out.println();
}
For n = 4, print both solutions and verify by inspection that no two queens share a row, column, or diagonal. This manual check is fast and catches subtle bugs in the diagonal tracking logic that a size check alone won't reveal.
10. Key Lessons for Future Problems
Reframing to simplify the problem is an important step. The observation that each row must contain exactly one queen turns a 2D placement problem into a sequence of 1D decisions. The solution follows almost directly from that reframe. Time spent thinking before coding is rarely wasted on this class of problem.
Constraints can be tracked with math. The row - col and row + col identifiers for diagonals are elegant and O(1). The general lesson: before reaching for a loop to check a constraint, ask whether the constraint can be captured algebraically. Often it can, and the savings are significant.
Tight constraints make backtracking fast. Backtracking has exponential worst-case complexity, but N-Queens shows that tight pruning can make it practical. The column and diagonal sets eliminate most candidates at each row, so the actual number of nodes explored is a small fraction of the theoretical maximum. When constraints are strong and applied early, backtracking stops being "brute force with undo" and becomes genuinely efficient search.
The choose/explore/un-choose symmetry is a correctness check. Every modification to shared state before a recursive call must be mirrored by a restoration after it. Counting your add/remove pairs and verifying they match is a fast way to catch bugs before testing.
N-Queens isn't about chess. It's about knowing when a placement is valid, exploring only valid paths, and undoing decisions cleanly. Those skills transfer everywhere.
Good Luck and Happy Coding!
Comments