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.
先从这个心智模型开始
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.
它如何工作，不堆砌不必要的术语
Place one queen per row.
Track occupied columns and diagonals with sets/bitmasks, recurse to the next row, then undo the choice.
把算法读成一连串决策
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;
}不要死记语法。跟踪每一行中发生变化的状态，并把它与上面描述的不变量联系起来。
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.
适用场景
- Use the recognized pattern when its invariant matches the problem constraints.
通常哪里会出错
- Jumping to code before defining the invariant.
- Optimizing before producing a correct baseline.
专业回答结构
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.
关于复杂度应该提到什么？
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.
最常见的错误是什么？
Jumping to code before defining the invariant.