Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Place n queens on an n×n board so none attack another, and return every distinct board. The canonical answer is backtracking row by row: each row holds exactly one queen, so try each column, prune any square attacked on its column or either diagonal using three boolean sets (cols, r+c, r−c), choose → recurse to the next row → un-choose. When you place a queen in the last row, build and record the board.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you shrink the search space by placing one queen per row, encode the three attack directions as O(1) set lookups (especially the `r+c` / `r−c` diagonal identities), and keep choose/un-choose perfectly symmetric. Bonus: tracking only one column per row instead of a full grid.
Where candidates slip
Re-scanning the whole board for conflicts (O(n) per check instead of O(1)), getting the diagonal formulas wrong (or only checking one diagonal), forgetting to also check rows (avoided automatically by the one-queen-per-row structure), or asymmetric backtracking that fails to clear all three marks.
How to stand out
State the one-queen-per-row reduction, derive WHY `row + col` and `row − col` identify the two diagonals, use boolean sets for O(1) pruning, keep choose/un-choose symmetric, and quote the bound (≈ O(n!) with pruning) plus the int[] queens space optimisation.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Each level places the queen for one row; each edge picks a column. Branches whose square is attacked (same column or diagonal as an earlier queen) are pruned in red. Reaching row 4 with all queens placed is a solution (green).
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Row-by-Row Backtracking with Conflict Sets (Optimal)
1Hint 1Explore hintHide hint
n queens, n rows, no two in the same row → how many queens must each row hold? What does that let you fix about the search?
2Hint 2Explore hintHide hint
Place row by row. For the queen in `row`, try each `col`. You need an O(1) way to ask 'is this square attacked by an earlier queen?' — what three things must be free?
3Hint 3Explore hintHide hint
Track used columns in a set, and the two diagonal families: all cells on a ↘ diagonal share `row + col`, all on a ↙ anti-diagonal share `row − col`. Mark all three on choose, clear all three on un-choose.
A · Core idea
Search the board one row at a time. Since a valid solution has exactly one queen per row, the only decision at depth row is which column that row's queen occupies. For each candidate col we ask: is (row, col) attacked by any queen already placed in rows above? If safe, we choose it (mark its column and both diagonals), explore by recursing to row + 1, then un-choose (clear those marks). When row == n we've safely placed all n queens, so we materialise the board and record it.
Why place one queen per row — the search-space reduction. A naive search over all C(n², n) ways to drop n queens on the board is astronomically large. But 'no two queens share a row' plus 'n queens on n rows' forces exactly one queen per row. Committing to that up front collapses the search to 'pick a column for each row', i.e. essentially a permutation search of size n! — and the row constraint is now satisfied by construction, so we never even check it. This reframing from 'choose cells' to 'choose one column per row' is the single most important modelling step.
Why `row + col` and `row − col` identify the diagonals. A queen attacks along both diagonals, so we must detect diagonal conflicts in O(1). Observe the geometry: as you walk down-right along a ↘ diagonal, row increases by 1 and col increases by 1, so row − col stays constant — every cell on a given ↘ diagonal shares the same row − col value. Symmetrically, walking down-left along a ↙ anti-diagonal, row increases while col decreases, so row + col stays constant. So 'is this square on a diagonal already occupied?' becomes two set-membership tests: (row − col) in antiDiag and (row + col) in diag. (In array-based variants, offset row − col by n − 1 to keep indices non-negative.) Combined with a cols set, three O(1) checks fully decide safety.
Why choose and un-choose must be perfectly symmetric. Placing a queen marks three things: its column, its row + col diagonal, and its row − col anti-diagonal. The backtracking discipline demands that returning from the recursion clears exactly those three marks — no more, no less. If you forget to clear even one (say the anti-diagonal), that line stays 'occupied' for every sibling and ancestor branch, and you'll silently miss valid solutions. The cleanest way to guarantee symmetry is to write the three marks and the three un-marks as mirror-image blocks around the recursive call.
Why store one column per row, not the whole grid. During the search we only need to know, per row, which column holds the queen — an int[] queens of length n captures the entire state and makes un-choosing trivial. We don't need the full n×n character grid until we actually record a solution, at which point we build the strings from queens. This keeps the working state O(n) instead of O(n²) and avoids mutating a big grid on every step.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4Interactive diagram
Why row+col and row−col name the diagonals
row 0Cells on the same ↘ diagonal share a constant row−col; cells on the same ↙ anti-diagonal share a constant row+col. That's what turns a diagonal attack check into an O(1) set lookup.
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]C · Code with teaching comments
D · Why it works and complexityO(n!) with diagonal pruning timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
N-Queens teaches the two universal levers of constraint-satisfaction backtracking: (1) structure the search so one constraint is satisfied by construction (one queen per row removes the row check entirely), and (2) make the remaining conflict tests O(1) with the right encoding (column and the two diagonal sums). The same playbook — fix one dimension, encode conflicts cheaply, prune early — is exactly how you'd attack Sudoku Solver or any grid-placement puzzle.
ComplexityO(n!) with diagonal pruning time, O(n) space — Placing one queen per row gives at most n choices in row 0, n−1ish in row 1 after pruning, etc., bounded by n! leaves; diagonal/column pruning cuts this dramatically in practice. Each placement check is O(1) via the sets, and building a solution board is O(n²) but happens only at valid leaves. Extra space is the recursion depth (O(n)), the int[] queens (O(n)), and the three sets (O(n)) → O(n) total, excluding output.
E · Edge cases and pitfalls6n = 1 — row 0 places (0,0); no conflicts possible; row == 1 → record ["Q"]. Returns [["Q"]].Explore edge casesHide edge cases
Edge cases handled
n = 1row 0 places (0,0); no conflicts possible; row == 1 → record ["Q"]. Returns [["Q"]].n = 2 (and n = 3)Every column choice in row 0 leaves no safe square in a later row → all branches pruned, returns []. Confirms the prune correctly reports impossibility.
Pitfalls
- Re-scanning the whole board for conflicts (O(n) per check) instead of O(1) set lookups — turns a fast search slow.
- Wrong diagonal formula or checking only one diagonal — produces attacking 'solutions'.
- Asymmetric backtracking: marking three lines but failing to clear all three — silently drops valid solutions.
- Negative array index for the anti-diagonal — remember the `+ (n − 1)` offset (a set avoids this entirely).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<List<String>> solveNQueens(int n) { List<List<String>> results = new ArrayList<>(); int[] queens = new int[n]; // queens[r] = column of the queen in row r boolean[] cols = new boolean[n]; boolean[] diag = new boolean[2 * n - 1]; // index by row + colExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Scanning the board for conflicts
Walking the column and both diagonals on every candidate is O(n) per check, making the inner work O(n) heavier than needed. Boolean sets answer 'attacked?' in O(1).
Explore the code comparisonHide the code comparison
Scanning the board for conflicts
Walking the column and both diagonals on every candidate is O(n) per check, making the inner work O(n) heavier than needed. Boolean sets answer 'attacked?' in O(1).
Don't write this
def is_safe(row, col):
for r in range(row): # O(n) scan per candidate
c = queens[r]
if c == col or abs(c - col) == abs(r - row):
return False
return TrueWrite this instead
if col in cols or (row + col) in diag or (row - col) in anti_diag:
continue # O(1) checks via sets2Asymmetric backtracking
Choosing marks col, row+col and row−col. If un-choose forgets even one (here the anti-diagonal), that line stays occupied for sibling branches and valid boards are silently lost.
Explore the code comparisonHide the code comparison
Asymmetric backtracking
Choosing marks col, row+col and row−col. If un-choose forgets even one (here the anti-diagonal), that line stays occupied for sibling branches and valid boards are silently lost.
Don't write this
cols.add(col); diag.add(row + col); anti_diag.add(row - col)
backtrack(row + 1)
cols.remove(col); diag.remove(row + col) # forgot anti_diag!Write this instead
cols.add(col); diag.add(row + col); anti_diag.add(row - col)
backtrack(row + 1)
cols.remove(col); diag.remove(row + col); anti_diag.remove(row - col)3Wrong diagonal identity
Cells on a ↘ diagonal share row−col, and ↙ anti-diagonals share row+col. Swapping them or only tracking one direction lets diagonally-attacking queens coexist.
Explore the code comparisonHide the code comparison
Wrong diagonal identity
Cells on a ↘ diagonal share row−col, and ↙ anti-diagonals share row+col. Swapping them or only tracking one direction lets diagonally-attacking queens coexist.
Don't write this
if (row + col) in diag: # only one diagonal family checked
continueWrite this instead
if (row + col) in diag or (row - col) in anti_diag: # both directions
continueRevise
Carry the pattern into the interview
Pattern to remember
Row-by-row backtracking with O(1) conflict sets (choose → explore → un-choose)
Code pattern to memorize
def backtrack(row):
if row == n: results.append(build()); return
for col in range(n):
if col in cols or (row+col) in diag or (row-col) in anti: continue # prune attacks
place(row, col) # choose: mark col, row+col, row-col
backtrack(row + 1) # explore the next row
remove(row, col) # un-choose: unmark all threeRules to remember
- 1Place one queen per row and recurse by row — this bakes in the 'no two queens share a row' rule for free.
- 2A square
(row, col)is safe iff its column, its `row + col` diagonal, and its `row − col` anti-diagonal are all unused — three O(1) set checks. - 3All cells on a ↘ diagonal share the same
row + col; all cells on a ↙ anti-diagonal share the samerow − col— that's why those two sums identify diagonals. - 4Choose and un-choose must be symmetric: marking col, r+c, r−c on the way down means unmarking all three on the way back up.
- 5Record only at
row == n— a complete, non-attacking placement of all n queens. - 6Track only one column per row (an
int[] queens), not the full grid — reconstruct the board strings only when you record.
Use this pattern when
- A constraint-satisfaction placement: put k items on a grid with no-conflict rules
- Conflicts are checkable incrementally as you place each item
- You need all valid configurations (or, for LC 52, the count)
- The board/grid is small enough that exponential search with pruning is fine
Choose another pattern when
- Only the **count** is needed and n is large → symmetry/known-formula tricks, or it's N-Queens II (still backtracking but no board build)
- Conflicts can't be tested until the whole configuration is placed → pruning can't help; rethink the model
- It's really a matching/flow problem in disguise → bipartite matching may beat brute search
- n is large (≳ 15–20) → the search explodes; the problem likely wants counting heuristics, not enumeration
Interview takeaway
N-Queens is the canonical constraint-satisfaction backtracking problem. The two ideas that make it click — reduce the search by placing one queen per row, and test conflicts in O(1) with the column / `r+c` / `r−c` sets — recur in Sudoku Solver and any 'place items with no-conflict rules' puzzle. Master the symmetric choose/un-choose with diagonal math here and the whole family follows.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Constraint-Satisfaction Backtracking (choose → explore → un-choose) with O(1) conflict sets. Recognise it whenever you place items on a grid under no-conflict rules. The two levers — structure the search so one constraint holds by construction (one queen per row), and encode the rest as O(1) checks (column, row+col, row−col) — also drive Sudoku Solver and Word Search.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- N-Queens IIComing soonOnly the COUNT of solutions is needed → identical row-by-row search, but increment a counter at row == n instead of building and storing boards.
- Sudoku SolverComing soonSame constraint-satisfaction backtracking — fill cells one at a time, prune with row/column/box sets, choose/explore/un-choose.
- Word SearchGrid backtracking with a visited marker — choose a cell, explore neighbours, un-choose; the same mark/unmark discipline as the queen conflict sets.
- PermutationsN-Queens is essentially a constrained permutation (column per row) — the used[]-style tracking and full-length leaf recording are the same core.