The n-queens puzzle places n queens on an n x n chessboard so that no two queens attack each other — no two share a row, column, or diagonal.
Given an integer n, return all distinct solutions. Each solution is a board drawn as an array of n strings, where 'Q' marks a queen and '.' marks an empty square. Solutions may be returned in any order, and the rows within each board run top to bottom.
Example
There are exactly two distinct ways to place four non-attacking queens on a 4×4 board.
Constraints
- 1 <= n <= 9
Intuition
A first attempt places one queen per row, same as the optimal search, but decides whether a column is safe by looking at the board itself: scan every queen already placed and check whether it shares the candidate's column or either diagonal.
function solveNQueensBruteForce(n) {
const result = [];
const queens = []; // queens[r] = column of the queen placed in row r
// Scan every already-placed queen for a column or diagonal collision — O(row) per call.
function isSafe(row, col) {
for (let r = 0; r < row; r++) {
const c = queens[r];
if (c === col) return false; // same column
if (Math.abs(c - col) === row - r) return false; // same diagonal, either direction
}
return true;
}
function place(row) {
if (row === n) {
// Every row is filled — turn the column list into the board's string form.
result.push(queens.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - 1 - c)));
return;
}
for (let col = 0; col < n; col++) {
if (!isSafe(row, col)) continue; // rescans the whole placed list every time
queens.push(col); // choose
place(row + 1); // explore with a queen locked in at (row, col)
queens.pop(); // un-choose before trying the next column
}
}
place(0);
return result;
}This already explores the right search tree — one queen per row, try a column, recurse, undo — so it isn't a different algorithm, just a slower way to answer one question: does this column collide with any queen already on the board? Scanning up to row placed queens for that answer costs O(n) in the worst case, and it gets asked at every one of the up to n candidate columns, at every one of the n rows — an avoidable O(n) factor stacked on top of an already-exponential search. Can we do better?
The key observation: a queen at (r, c) doesn't just occupy one column — it also occupies exactly one "↘" diagonal, where r − c is constant, and one "↙" diagonal, where r + c is constant. Column and both diagonals are just three group memberships, and answering membership in O(1) is exactly the hash maps trick — keep three Sets (cols, diag1 keyed by r − c, diag2 keyed by r + c) instead of rescanning the board.
The stored solution keeps the identical recursive shape — same row-by-row placement, same push/recurse/pop — and only swaps the O(n) board rescan for three O(1) set lookups, adding to and removing from the three sets alongside every queens.push() / queens.pop().
Walking it through:
n = 4
Start the search: row 0 has no queens yet, so column 0 is automatically safe. Place the queen and record cols={0}, diag1={0} (0−0), diag2={0} (0+0).
(1,1) sits on (0,0)'s ↘ diagonal (r − c = 0, the whole diagonal is marked) — the diag1 set rejects it in O(1), no need to look at the board.
Column 2 collides with nothing — not (0,0)'s column, and neither of its diagonals. Place the queen and recurse into row 2.
Column 0 shares (0,0)'s column; column 1 shares (1,2)'s ↙ diagonal (r+c=3); column 2 shares (1,2)'s column; column 3 shares (1,2)'s ↘ diagonal (r−c=−1). No safe cell — pop (1,2). Row 1's last option, column 3, dead-ends the same way one row deeper, so the whole column-0 opening backtracks out completely; row 0 retries with column 1.
Under the new queen at (0,1), row 1 rules out column 0 (shares its ↙ diagonal, r+c=1), column 1 (shares its column), and column 2 (shares its ↘ diagonal, r−c=−1) — the same three set checks as before — leaving column 3 clear. Row 2 then finds column 0 open. Three queens placed, one row left.
Column 2 collides with none of the three queens above it. All four rows are filled, so this board — one of N-Queens' two solutions for n = 4 — is recorded.
Optimization
Backtracking with diagonal sets
Place one queen per row. Track occupied columns and both diagonal directions in sets: a queen at (r, c) owns column c, the "↘" diagonal r - c, and the "↙" diagonal r + c. For each row try every safe column, recurse to the next row, and record a board when all n rows are filled. The set lookups make each safety check O(1).
Time is O(n!) in the worst case (bounded hard by the pruning), O(n) extra space for the recursion and sets.
function solveNQueens(n) {
const result = [];
const queens = []; // queens[r] = column of the queen placed in row r
const cols = new Set(); // columns already occupied
const diag1 = new Set(); // "↘" diagonals occupied, keyed by r - c (constant along that diagonal)
const diag2 = new Set(); // "↙" diagonals occupied, keyed by r + c (constant along that diagonal)
const place = (row) => {
if (row === n) {
// Every row holds a queen — turn the column list into the board's string form.
result.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - 1 - c)));
return;
}
for (let c = 0; c < n; c++) {
// O(1) safety check: same column, or either diagonal through (row, c).
if (cols.has(c) || diag1.has(row - c) || diag2.has(row + c)) continue;
cols.add(c); diag1.add(row - c); diag2.add(row + c); queens.push(c); // choose
place(row + 1); // explore with a queen locked in at (row, c)
cols.delete(c); diag1.delete(row - c); diag2.delete(row + c); queens.pop(); // un-choose before the next column
}
};
place(0);
return result;
}Complexity analysis
Time complexity: O(n!). Here's why:
- Row 0 has up to
ncandidate columns; row 1 has at mostn − 1left once one column is ruled out, and so on — the search tree branches like a permutation of thencolumns, one per row. - The three
Sets prune many branches long before they reach rown, but the classic worst-case bound is still the same as generating permutations ofncolumns: O(n!). - Each safety check inside the loop is O(1) (three set lookups), so checking itself adds no extra factor on top of the branching — the brute force's O(n) rescan is what the sets remove.
So the overall time is bounded by O(n!), dominated by the shape of the search tree.
Space complexity: O(n) auxiliary. Here's why:
queensholds at mostncolumn choices, one per row.cols,diag1, anddiag2each hold at mostnentries — one per placed queen.- The recursion stack is at most
nframes deep, one per row.
So the extra bookkeeping is O(n). The result array can hold up to as many boards as exist for that n, each an array of n strings — that's the required output, not overhead the algorithm adds.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| n = 1 | [["Q"]] | Trivial base case — a single queen on a 1×1 board has no possible conflicts. |
| n = 2 | [] | Smallest no-solution board — every column choice at row 1 collides with row 0's queen, by column or diagonal. |
| n = 3 | [] | Still no solution — three queens can't avoid attacking each other on a 3×3 board. |
| n = 4 | [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] | Smallest board with a solution — exactly two, mirror images of each other. |
Try it yourself
Write your solution against the real judge before checking the reference.