The N-Queens puzzle asks you to place n queens on an n x n chessboard so that no two queens attack each other. A queen attacks along its entire row, its entire column, and both diagonals.
Given an integer n, return all distinct ways to place the queens. You may return the boards in any order.
Each solution is a board drawn as n strings of length n, where 'Q' marks a queen and '.' marks an empty square.
row - col (or row + col) values match — turn each constraint into a set you can check in O(1).'Q' marks a queen and '.' marks an empty square. Every board string is length n and uses only those two characters.row == n.Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] There are exactly two ways to place 4 non-attacking queens on a 4x4 board.
Input: n = 1 Output: [["Q"]] A single queen on a 1x1 board attacks nothing.
- 1 <= n <= 9
Placing queens on a chessboard so that none can attack another is the hello world of backtracking — a problem where trying, failing, and undoing is the entire algorithm. We'll go from a board-scanning search to a version that tests every placement in O(1).
row - col; cells on the same up-right diagonal share row + col.Formally: put n queens on an n x n board so that no two share a row, a column, or a diagonal, and return every distinct board as n strings of 'Q' and '.'.
Because two queens on the same row always attack, each row holds exactly one queen — so a full board is simply a choice of one column per row.
Worked example — n = 4
One valid board (columns chosen per row: 1, 3, 0, 2) . Q . . row 0 -> col 1 . . . Q row 1 -> col 3 Q . . . row 2 -> col 0 . . Q . row 3 -> col 2 No two queens share a column or a diagonal. OK
Asking before coding shows you map the input space before touching a keyboard.
“Is each board n strings of Q and dot, and can the boards come in any order?”
Confirms the exact shape you must return and that solutions need no particular order.
“What should n = 1 return?”
A single queen on a 1x1 board is a valid solution — the base case must not be skipped.
“What about an n with no solution, like 2 or 3?”
The function must return an empty list, not error out.
“How large can n get?”
With n up to 9 the search space is tiny, so a clean backtracking solution comfortably fits the limits.
Before I code, a few quick checks on the output and the edges.
Each solution is n strings of Q and dot, and the boards can come in any order — right?
And for an n where no arrangement exists, like 2 or 3, I return an empty list rather than throwing.
Two queens in the same row always attack, so every row has exactly one queen. Instead of choosing n cells out of n², we choose a single column for row 0, then row 1, and so on — a far smaller tree.
Every cell on the same down-right diagonal shares row - col; every cell on the same up-right diagonal shares row + col. So a diagonal clash is one lookup, not a walk across the board.
row - col (down-right) row + col (up-right) 0 1 2 3 0 1 2 3 -1 0 1 2 1 2 3 4 -2 -1 0 1 2 3 4 5 -3 -2 -1 0 3 4 5 6
The instant a column, a down-right diagonal, or an up-right diagonal is already occupied, skip that cell — never recurse into a doomed branch. This pruning is what keeps the search fast.
| Brute force | Optimal | |
|---|---|---|
| Conflict test | scan all placed rows, O(n) | set lookup, O(1) |
| Time | O(n! · n) | O(n!) |
| Space | O(n) | O(n) |
Both walk the same decision tree; the optimal one just answers "is this cell safe?" in constant time. Full code is in the Approaches selector below.
Key takeaway
N-Queens is the template for constraint backtracking: place one unit per row, encode each constraint (column, down-right diagonal, up-right diagonal) as a fast membership test, and undo on the way back up. Master this and grid-placement puzzles all start to look the same.
solve(row):
if row == n: record board; return
for col in 0..n-1:
if col, row-col, row+col all free:
place queen; mark the three sets
solve(row + 1)
remove queen; unmark the three sets