N-Queens Problem
N-Queens places N queens on an N×N chessboard so that no two share a row, column or diagonal. Backtracking explores choices and abandons partial boards as soon as a conflict appears.
Start with this mental model
N-Queens places N queens on an N×N chessboard so that no two share a row, column or diagonal. Backtracking explores choices and abandons partial boards as soon as a conflict appears.
How it works, without unnecessary jargon
Place one queen per row.
Track occupied columns and diagonals with sets/bitmasks, recurse to the next row, then undo the choice.
Read the algorithm as a sequence of decisions
Restate constraints and edge cases.
Identify the pattern and invariant.
Walk through a small example before coding.
Read a tiny input by hand and write down the state after every important operation. For N-Queens Problem, the goal is to make the invariant visible rather than to memorize code.
function solveNQueens(n) {
const cols = new Set(), diag1 = new Set(), diag2 = new Set();
const board = Array(n).fill(-1), solutions = [];
function place(row) {
if (row === n) { solutions.push([...board]); 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); board[row] = col;
place(row + 1);
cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
}
}
place(0);
return solutions;
}Do not memorize the syntax. Follow the state that changes on each line and connect it to the invariant described above.
Varies by implementation / input constraints
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
Good fit
- Use the recognized pattern when its invariant matches the problem constraints.
What usually goes wrong
- Jumping to code before defining the invariant.
- Optimizing before producing a correct baseline.
A professional answer shape
The important part is pruning: backtracking is not brute-force enumeration of complete boards; it rejects impossible prefixes early.
What problem does N-Queens Problem solve?
N-Queens places N queens on an N×N chessboard so that no two share a row, column or diagonal. Backtracking explores choices and abandons partial boards as soon as a conflict appears.
What should I mention about complexity?
Its typical cost here is Varies by implementation / input constraints, but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
What is the most common mistake?
Jumping to code before defining the invariant.