N-Queens
Place n queens on an n × n board so none attack each other with backtracking: one queen per row, and sets for columns and both diagonals.
Problem Understanding
N-Queens: place n queens on an n × n chessboard so that no two attack each other (no shared row, column or diagonal). Return every distinct board, written as strings with Q for a queen and . for an empty square.
Example: n = 4 has 2 solutions: [".Q..", "...Q", "Q...", "..Q."] and its mirror image.
The Intuition: One Queen per Row, Three Sets
Every solution has exactly one queen in each row, so decide rows one at a time with backtracking: for row r, choose a column.
A column choice is safe only if no earlier queen shares:
- its column
c, - its diagonal, where every square has the same
r − c, - its anti-diagonal, where every square has the same
r + c.
Three sets answer all three questions in O(1). Place a safe queen, mark its three values, recurse into the next row, then unmark them and try the next column. It is the same choose / explore / un-choose template as Permutations, with pruning that cuts most branches early.
Interactive Walkthrough
Queens are drawn as ♛ and every square they attack is shaded, so a blocked try always lands on a shaded square. Each solution is listed beside the board as the queen's column in every row. Try n = 3 to watch every branch dead-end, and n = 5 for 10 solutions.
Dry Run Table
Input: n = 4 (columns 0–3)
| Row | Tried | Result |
|---|---|---|
| 0 | 0 | place |
| 1 | 0, 1 blocked; 2 | place |
| 2 | 0–3 all blocked | backtrack to row 1 |
| 1 | 3 | place |
| 2 | 1 | place |
| 3 | 0–3 all blocked | backtrack to row 0 |
| 0 | 1 | place, then 3, 0, 2: solution [1, 3, 0, 2] |
| 0 | 2 | mirror image: solution [2, 0, 3, 1] |
Answer: 2 boards.
The Solution Template
Row-by-row backtracking with column and diagonal sets. Java, C++ and C index diagonals as r − c + n so they stay non-negative.
N-Queens Code
1var solveNQueens = function(n) {2 const res = [], queens = [];3 const cols = new Set(), diag = new Set(), anti = new Set();4 const place = (r) => {5 if (r === n) {6 res.push(queens.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));7 return;8 }9 for (let c = 0; c < n; c++) {10 if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;11 cols.add(c); diag.add(r - c); anti.add(r + c); queens.push(c);12 place(r + 1);13 cols.delete(c); diag.delete(r - c); anti.delete(r + c); queens.pop();14 }15 };16 place(0);17 return res;18};
Edge Cases & Common Mistakes
- n = 2 or 3: there is no solution; return an empty list.
- Negative diagonal index:
r − ccan be negative; offset it bynwhen using arrays. - Forgetting to unmark: remove the column and both diagonals after the recursive call, or later branches see phantom queens.
- Checking the whole board: scanning all earlier queens works but costs O(n) per check; the three sets make it O(1).
- N-Queens II (LeetCode 52): the same search, counting solutions instead of building boards.
Summary
Place one queen per row. For each column, skip it if its column, r − c diagonal or r + c anti-diagonal is taken; otherwise mark all three, recurse to the next row, and unmark on the way back. Reaching row n records a board. O(n!) time, O(n) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet