N-Queens — all solutions

Hard

Problem

Place n queens on an n × n board so that no two attack each other (same row, column or diagonal). Return every distinct board.

Example 1

Input:  n = 4
Output: [".Q..","...Q","Q...","..Q."] and ["..Q.","Q...","...Q",".Q.."]

Also asked as: Printing all solutions in N-Queen Problem

Test cases

Case 1

Input:    4
Expected (any order): [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Case 2

Input:    1
Expected (any order): [["Q"]]

Case 3

Input:    3
Expected (any order): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Row-by-row with column & diagonal sets

Time O(N!)Space O(N)

Place one queen per row. A column is free if it is not in `cols`, and diagonals are tracked by r−c and r+c. Recurse, backtrack.

function solveNQueens(n) {
const res = [], pos = [];
const cols = new Set(), d1 = new Set(), d2 = new Set();
const bt = (r) => {
if (r === n) { res.push(pos.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))); return; }
for (let c = 0; c < n; c++) {
if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue;
cols.add(c); d1.add(r - c); d2.add(r + c); pos.push(c);
bt(r + 1);
cols.delete(c); d1.delete(r - c); d2.delete(r + c); pos.pop();
}
};
bt(0);
return res;
}