LeetCode 51 ·
Hard
N-Queens
Place n queens on an n×n board so none attack each other; return all solutions.
Try it
Step through the core mechanic. The simulator below runs the backtracking shape this problem is built on.
Interactive · Recursion call tree — Fibonacci naive recomputes; memoised short-circuits on cache hits
Mode O(2ⁿ) calls
enter fib(6)
total calls1 unique values≤ 7 modenaive
Toggle the modes.
Naive at n=6 makes 25 calls. Memoised at n=6 makes 11 calls — and the cache
hits (amber circles) are the difference. The shape of the tree changes
dramatically: naive is a fat exponential tree; memoised collapses to a
near-linear path with stub returns where the cache hits.
The approach
Place one queen per row, backtracking. Track occupied columns and both diagonals (col, row−col, row+col) in sets for O(1) conflict checks. Undo on backtrack.
| Aspect | Value |
|---|---|
| Pattern | Backtracking |
| Recognise it by | Place n non-attacking queens. |
| Time complexity | O(n!) |
| Space complexity | O(n) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.