How do you solve the N-Queens problem with backtracking?
Place one queen per row. For each column in the row, check that no earlier queen shares the column or a diagonal. If safe, place it and recurse to the next row; otherwise skip. Undo and try the next column.
Explain it simply
On a chessboard, a queen attacks along its row, column and both diagonals. You must place N queens so none attack each other.
Since each row holds exactly one queen, you only choose a column per row. Track which columns and diagonals are taken. Two cells share a diagonal when row - col is equal (one diagonal direction) or row + col is equal (the other). If a row has no safe column, you backtrack to the previous row and move that queen.
Example
function countNQueens(n) {
const cols = new Set();
const diag1 = new Set(); // row - col
const diag2 = new Set(); // row + col
let count = 0;
function place(row) {
if (row === n) {
count++;
return;
}
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
place(row + 1);
cols.delete(col);
diag1.delete(row - col);
diag2.delete(row + col);
}
}
place(0);
return count;
}
console.log(countNQueens(4)); // Output: 2
console.log(countNQueens(6)); // Output: 4
console.log(countNQueens(8)); // Output: 92Complexity
Time exponential (roughly O(N!) with pruning), space O(N).
What to say in the interview
"I place one queen per row and keep sets for used columns and for the two diagonal directions, row minus column and row plus column. If a column is safe I place the queen, recurse to the next row and then undo it. Pruning keeps it far below N to the power N; the exact worst case is still exponential."
Common mistakes
- Checking diagonals by scanning the whole board each time instead of using sets.
- Forgetting to remove entries from the sets when backtracking.