02. N-Queens
The N-Queens puzzle requires placing n queens on an $n \times n$ chessboard such that no two queens attack each other. Return all distinct board configurations.
How It Works & Algorithmic Design
Solves using DFS Backtracking with Sets:
- Conflict Sets: Maintain sets for used
cols, main diagonals (r - c), and anti-diagonals (r + c). - Row Placement DFS: Place queens row by row. For each row $r$, test column $c$:
- If column or diagonals are occupied, skip.
- Place queen, mark conflict sets, and recurse to row $r + 1$.
- Backtrack: remove queen and unmark sets.
Why This Approach Works Best
Set lookups determine placement safety in $O(1)$ time, reducing the search space to $O(n!)$ time.
Example Walkthrough
Input:
n = 44x4 chessboard.
Valid Layouts:
Distinct solutions placing 4 non-attacking queens.No shared rows, columns, or diagonals.
Output:
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]2 distinct arrangements.
Answer: N-Queens Backtracking implementation
function solveNQueens(n) {
const res = [];
const cols = new Set(), diag = new Set(), antiDiag = new Set();
const board = Array.from({ length: n }, () => new Array(n).fill('.'));
function backtrack(r) {
if (r === n) {
res.push(board.map(row => row.join('')));
return;
}
for (let c = 0; c < n; c++) {
if (cols.has(c) || diag.has(r - c) || antiDiag.has(r + c)) continue;
cols.add(c); diag.add(r - c); antiDiag.add(r + c);
board[r][c] = 'Q';
backtrack(r + 1);
cols.delete(c); diag.delete(r - c); antiDiag.delete(r + c);
board[r][c] = '.';
}
}
backtrack(0);
return res;
}💡 Recursively place queens row by row while checking column and diagonal conflict sets.
Key Takeaways
- Main diagonal identity is $r - c$; anti-diagonal identity is $r + c$.
- Set lookups prune invalid attack positions in $O(1)$ time.
- Overall execution takes $O(n!)$ time.