Pattern this teaches:Backtracking with Constraints
N-Queens
A hard Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 3
- Core for
- 0 roles
The problem
Place n queens on an n x n chessboard so that no two of them share a row, a column or a diagonal. Return every such placement, drawing each board as a list of strings where 'Q' marks a queen and '.' an empty square.
Example 1
- Input
- n = 4
- Output
- [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
- Why
- There are two distinct solutions for a 4×4 board. In each, queens are placed so no two share a row, column, or diagonal.
Example 2
- Input
- n = 1
- Output
- [["Q"]]
- Why
- A single queen on a 1×1 board is the only solution.
Constraints
- 1 <= n <= 9
How to think about it
Updated 2026-09-29Every row must hold exactly one queen, so you can place queens row by row from 0 to n - 1. Diagonals have constant algebraic invariants: major diagonals share constant row - col, and minor diagonals share constant row + col. Hashing these invariants turns conflict checking from a board scan into O(1) set lookups.
Approaches, worst first
Full board raycasting
time O(n!) · space O(n^2)
Place a queen row by row. Before placing at (row, col), scan upward through the column and both upper diagonals cell-by-cell to confirm no queen attacks it. Correct, but spends O(n) checking validity at every single cell candidate.
Lookup sets for diagonals
time O(n!) · space O(n)
Maintain boolean arrays or integer sets for cols, diag1 (row - col), and diag2 (row + col). Validating a column candidate becomes three O(1) lookups. When valid, mark the sets, recurse to row + 1, and unmark on return.
Bitmask trackingWrite this one
time O(n!) · space O(n)
Represent occupied columns and diagonals as bitmasks in integers. As row increases, shift left diagonal mask left and right diagonal mask right. Bitwise operations isolate open columns in O(1) without hash lookups or array indexing.
Where people lose marks · 3
- Negative indices in array-based diagonal tracking. Because row - col ranges from -(n - 1) to +(n - 1), indexing an array directly without adding an offset of n - 1 causes an out-of-bounds error.
- Placing multiple queens on the same row: iterating over all n * n cells instead of row by row explodes the search space to C(n^2, n) instead of n!.
- Assuming n = 2 or n = 3 have solutions; the algorithm must cleanly return empty arrays without hanging or throwing errors.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .