Problem overview
The method solveNQueens receives an integer n and must place n queens on an n x n chessboard so that no two queens attack each other. A queen attacks along its row, its column and both diagonals. The method returns every distinct solution, in any order.
A solution is an array of length n in which element r is the column of the queen in row r. For n = 4 there are two solutions: [1, 3, 0, 2] and [2, 0, 3, 1]. In the first, the queens are at row 0 column 1, row 1 column 3, row 2 column 0 and row 3 column 2. The statement's limits are 1 <= n <= 9.
Approach: one queen per row, undo when stuck
Every row must hold exactly one queen: two in a row would attack each other, and with n rows and n queens none can be left over. That turns the puzzle into a sequence of choices. For row 0 choose a column, for row 1 choose a column, and so on. Trying all n to the power n combinations is wasteful, since most are wrong from the first few rows.
Backtracking prunes them early. Build the answer one row at a time, and put a queen in a square only if it is safe from the queens already placed. If a row has no safe square, return to the previous row and try its next column. When all n rows are filled, copy the placement into the results.
The pattern for each choice is always the same: add it, recurse, remove it. Removing the choice after the recursive call returns leaves the shared array exactly as it was, ready for the next column.
Checking whether a square is safe needs only the columns of the earlier rows. Rows cannot clash, because each row gets one queen. A new queen at (row, col) clashes with a queen at (i, placement[i]) in two cases:
- they share a column:
placement[i] == col; - they share a diagonal: the row distance equals the column distance,
Math.abs(row - i) == Math.abs(col - placement[i]).
Step by step
- Create the results list,
placements, of typenumber[][], empty at first. - Start the search with
this.backtracking(n, 0, [], placements): row 0, with nothing placed. - Return
placements. - Declare
backtrackingwithn,row,placementandplacements. Each call handles one row, andplacementholds the columns chosen for the rows above it. - Stop when the board is full. If
row == n, push a copy,[...placement], intoplacements, and return. The copy matters, as explained below. - Loop over the columns
colfrom 0 ton - 1. - Test the square with
this.isValid(placement, row, col). - Place the queen by pushing
colontoplacement. - Recurse into the next row with
this.backtracking(n, row + 1, placement, placements). - Undo the choice with
placement.pop(). - Write
isValidto return aboolean, true when the square is safe. - Scan the earlier rows
ifrom 0 torow - 1. The queen of rowisits atplacement[i]. - Return
falseon a clash: same column, or equal row and column distances. - Return
trueif the loop finds no conflict.
The solution in TypeScript
class Solution {
isValid(placement: number[], row: number, col: number): boolean {
for (let i = 0; i < row; i++) {
if (placement[i] == col ||
Math.abs(row - i) == Math.abs(col - placement[i])) {
return false;
}
}
return true;
}
backtracking(n: number, row: number, placement: number[], placements: number[][]) {
if (row == n) {
placements.push([...placement]);
return;
}
for (let col = 0; col < n; col++) {
if (this.isValid(placement, row, col)) {
placement.push(col);
this.backtracking(n, row + 1, placement, placements);
placement.pop();
}
}
}
solveNQueens(n: number): number[][] {
let placements: number[][] = [];
this.backtracking(n, 0, [], placements);
return placements;
}
}
TypeScript details worth knowing:
- Why copy with
[...placement].placementis one array that every call shares and keeps changing. Pushing it itself intoplacementswould store a reference to that array, and by the end of the search it is empty again, so every stored solution would show up as[]. The spread syntax creates a new array with the current elements. - Arrays as a stack.
pushadds at the end andpopremoves from the end, which is the add-and-undo pattern backtracking needs. - No return type on
backtracking. The method returns nothing, so TypeScript infersvoid. Writing: voidis allowed and is clearer. - Parameters are shared by reference. Arrays are objects, so changes made inside a recursive call are visible to the caller.
==on numbers behaves the same as===here.
Complexity
Time: exponential. There are at most n choices in the first row and fewer in the later ones, since each queen rules out squares. The exact count has no simple formula, but it is far below n^n, and it still grows quickly: the numbers of solutions for n = 1 to 9 are 1, 0, 0, 2, 10, 4, 40, 92, 352. That is why the lesson stops at n = 9. Each isValid call costs O(n).
Space: the recursion and the placement array are O(n) deep. The result itself holds one array of n numbers per solution, which dominates for larger n.
Edge cases and common mistakes
n = 1. One queen on a one-square board, so the result is[[0]].n = 2andn = 3. No arrangement works, so the result is[].- Forgetting
pop. The queen from the failed attempt stays inplacement, and later rows are checked against queens that are no longer there. - Pushing
placementwithout copying, as described above. - Checking only one diagonal. The test compares absolute distances so that both directions are covered. Without
Math.abs, only one diagonal direction is caught. - Checking the current row. The scan stops at
row - 1. The current row has no queen yet. - Result order. The loop tries columns from left to right, so the solutions come out in increasing order: for
n = 4,[1, 3, 0, 2]and then[2, 0, 3, 1]. Any order is accepted.
Testing
n = 1gives[[0]].n = 2andn = 3give[].n = 4gives[[1, 3, 0, 2], [2, 0, 3, 1]].n = 6gives 4 solutions, starting with[1, 3, 5, 0, 2, 4].n = 8gives 92 solutions, andn = 9gives 352.