Place n queens on an n×n board so no two attack each other. The canonical approach recurses one row at a time and uses three sets — columns, diagonals, and anti-diagonals — to prune illegal placements in O(1) per check.
Given an integer n, return all distinct solutions to the N-Queens puzzle: place n queens on an n×n chess board so that no two queens share a row, column, or diagonal.
Concrete example — n = 4: two solutions exist.
Solution 1 Solution 2 . Q . . . . Q . . . . Q Q . . . Q . . . . . . Q . . Q . . Q . .
Output is an array of boards; each board is an array of strings, e.g. [".Q..","...Q","Q...","..Q."].
row − col (the main diagonal) or row + col (the anti-diagonal). Storing both values in sets gives an O(1) conflict check— no board scanning needed. Place, recurse, remove. That's the whole algorithm.cols, diag (r-c), anti (r+c) and an array queens[]. All are empty.row === n, all queens are placed validly — serialize the board and push to results. Return.col in 0…n-1, skip if cols, diag, or anti contains the relevant key — this position is attacked.col onto queens, add col, row-col, and row+col to the three sets.backtrack(row + 1). The next level will try every column for the next row.queensand delete the three keys from their sets. This is the “undo” that makes backtracking work — the state must be exactly as it was before step 3.r - c (same value for cells running top-left to bottom-right) while the anti-diagonal uses r + c (same value top-right to bottom-left). Mixing them up or using only one will silently miss conflicts on one axis.Space is O(n) for the recursion stack and the three sets (each holds at most n entries). The output itself is output size — not counted in auxiliary space.
The number of solutions grows super-exponentially with n: n=4 has 2, n=8 has 92, n=14 has 365,596. In practice the pruning is extremely effective — the search tree is vastly smaller than n!.
n=4. Place one queen per row — track cols, r-c, and r+c sets to detect conflicts.1function solveNQueens(n: number): string[][] {2▶ const results: string[][] = [];3▶ const cols = new Set<number>();4▶ const diag = new Set<number>(); // r - c (top-left → bottom-right)5▶ const anti = new Set<number>(); // r + c (top-right → bottom-left)6▶ const queens: number[] = []; // queens[r] = column of queen in row r78 function backtrack(row: number): void {9 if (row === n) {10 // Build the board from the completed queen placement11 results.push(12 queens.map((c) =>13 '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)14 )15 );16 return;17 }18 for (let col = 0; col < n; col++) {19 if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;20 // Place21 queens.push(col);22 cols.add(col);23 diag.add(row - col);24 anti.add(row + col);2526 backtrack(row + 1);2728 // Remove (backtrack)29 queens.pop();30 cols.delete(col);31 diag.delete(row - col);32 anti.delete(row + col);33 }34 }3536 backtrack(0);37 return results;38}
cols: {}diag: {}anti: {}00 / 4[]function solveNQueens(n: number): string[][] {
const results: string[][] = [];
const cols = new Set<number>();
const diag = new Set<number>(); // r - c (top-left → bottom-right)
const anti = new Set<number>(); // r + c (top-right → bottom-left)
const queens: number[] = []; // queens[r] = column of queen in row r
function backtrack(row: number): void {
if (row === n) {
// Build the board from the completed queen placement
results.push(
queens.map((c) =>
'.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)
)
);
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
// Place
queens.push(col);
cols.add(col);
diag.add(row - col);
anti.add(row + col);
backtrack(row + 1);
// Remove (backtrack)
queens.pop();
cols.delete(col);
diag.delete(row - col);
anti.delete(row + col);
}
}
backtrack(0);
return results;
}cols tracks occupied columns; diag stores row - col for main diagonals; anti stores row + col for anti-diagonals. queens[r] records which column row r chose — used only at leaves to serialize.row === n every row has a queen; the placement is valid by construction (we never placed into a conflict). We serialize: for each row r, dot-pad around column queens[r] using string repetition.if checks all three conflict axes simultaneously. If any set contains the relevant key, this cell is attacked — continue to the next column. No board scan.queens and record the three keys into their sets. Then recurse into row row + 1.queens, delete the three keys. This undo is the defining move of backtracking — the loop can then try the next column with a clean slate.O(n!) in the worst case (each row prunes available columns). Space: O(n) auxiliary for the stack and sets (the output is separate). In practice the pruning makes it far faster than n! — n=8 explores only ~2,000 nodes out of 8! = 40,320.results array with a counter; remove the board serialization entirely. Same backtracking, tiny change.lowbit = x & (-x) to isolate the next available column in a single instruction. N=15 runs in milliseconds.backtrack; propagate true upward immediately on the first record, short-circuiting all remaining branches.function solveNQueens(n: number): string[][] {
const results: string[][] = [];
const cols = new Set<number>();
const diag = new Set<number>(); // r - c (top-left → bottom-right)
const anti = new Set<number>(); // r + c (top-right → bottom-left)
const queens: number[] = []; // queens[r] = column of queen in row r
function backtrack(row: number): void {
if (row === n) {
// Build the board from the completed queen placement
results.push(
queens.map((c) =>
'.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)
)
);
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
// Place
queens.push(col);
cols.add(col);
diag.add(row - col);
anti.add(row + col);
backtrack(row + 1);
// Remove (backtrack)
queens.pop();
cols.delete(col);
diag.delete(row - col);
anti.delete(row + col);
}
}
backtrack(0);
return results;
}O(n!) in the worst case (each row prunes available columns). Space: O(n) auxiliary for the stack and sets (the output is separate). In practice the pruning makes it far faster than n! — n=8 explores only ~2,000 nodes out of 8! = 40,320.Replace the three Sets with integer bitmasks and isolate each free column with free & (-free) — the fastest practical solver.
function solveNQueens(n: number): string[][] {
const results: string[][] = [];
const queens: number[] = []; // queens[r] = column chosen for row r
const all = (1 << n) - 1; // n low bits set = every column open
// cols, diag, anti are bitmasks of ATTACKED columns for the current row.
function backtrack(cols: number, diag: number, anti: number): void {
if (queens.length === n) {
results.push(
queens.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))
);
return;
}
// Bits that are 1 here are columns NOT attacked by any axis.
let free = all & ~(cols | diag | anti);
while (free !== 0) {
const bit = free & -free; // lowest set bit = next candidate column
free ^= bit; // consume it for this loop iteration
const col = Math.log2(bit) | 0; // index of that bit (0 .. n-1)
queens.push(col);
// Shift diag/anti by one: moving to the next row slides both diagonals.
backtrack(cols | bit, (diag | bit) << 1, (anti | bit) >> 1);
queens.pop();
}
}
backtrack(0, 0, 0);
return results;
}diag shifts left and anti shifts right each row because a diagonal threat moves one column over per row. Bits that slide past the board edge vanish automatically when masked by all. For n ≤ 31 the masks fit in a single 32-bit integer.Any permutation of column indices already places exactly one queen per row and column — so only the two diagonals need checking.
function solveNQueens(n: number): string[][] {
const results: string[][] = [];
const perm: number[] = []; // perm[r] = column of queen in row r
const used: boolean[] = new Array(n).fill(false);
// A permutation guarantees distinct rows AND columns automatically.
// Two queens conflict diagonally iff |r1 - r2| === |c1 - c2|.
function diagonalsOk(row: number, col: number): boolean {
for (let r = 0; r < row; r++) {
if (Math.abs(row - r) === Math.abs(col - perm[r])) return false;
}
return true;
}
function build(row: number): void {
if (row === n) {
results.push(
perm.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))
);
return;
}
for (let col = 0; col < n; col++) {
if (used[col]) continue; // enforce the permutation (unique columns)
if (!diagonalsOk(row, col)) continue;
used[col] = true;
perm.push(col);
build(row + 1);
perm.pop();
used[col] = false;
}
}
build(0);
return results;
}used[] flags keep columns distinct, leaving only diagonal validation. The diagonal scan is O(n) per placement, giving the O(n!·n) bound — clearer to reason about, but slower than the O(1) set or bitmask checks.| place items on a grid with mutual exclusion constraints | row-by-row backtracking + sets |
| count / enumerate all valid board arrangements | backtrack with base case at row === n |
| "no two on the same diagonal" | r-c set (main) and r+c set (anti) |
| need to undo a placement after exploring a subtree | add before recurse, delete after |
const cols = new Set<number>();
const diag = new Set<number>(); // r - c
const anti = new Set<number>(); // r + c
const queens: number[] = [];
function backtrack(row: number): void {
if (row === n) { /* record solution */ return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
queens.push(col); cols.add(col); diag.add(row - col); anti.add(row + col);
backtrack(row + 1);
queens.pop(); cols.delete(col); diag.delete(row - col); anti.delete(row + col);
}
}
backtrack(0);cols: occupied columns. diag: values of row - col (main diagonals). anti: values of row + col (anti-diagonals).diag set to detect main-diagonal conflicts?backtrack(row + 1) returns, you must:2, col 3. Which values are added to the three sets?