N 皇后
回溯与搜索 · 约束满足
在棋盘上摆皇后
在 N×N 棋盘上放 N 个皇后，让它们两两不能互相攻击——即任意两个皇后不在同一行、同一列、同一对角线上。有多少种摆法、怎么找到一种？这是回溯（backtracking）算法的经典范例：一个「试探 → 遇阻就退回重试」的通用套路。
回溯：试探、剪枝、回退
因为每列必有且只有一个皇后，我们逐列放置。在当前列从上到下试每一行：
能放吗？——检查这一格是否与已放的皇后冲突（同行 / 同对角线）。不冲突就放下，然后递归去放下一列；冲突就直接跳过这一行（这就是剪枝：不去尝试注定失败的分支）。如果一整列每一行都放不了，说明前面的选择有问题——回溯：退回上一列，把那里的皇后挪到下一个可行位置再往下试。
下面是 4×4 棋盘。点「下一步」逐步看：当前尝试的格琥珀高亮，若与某个皇后冲突，冲突的皇后变红、换下一行；不冲突就放下 ♛ 进入下一列；一列走投无路就撤掉上一列的皇后回溯。经过几次试错，最终摆出一个合法解。右侧代码随每一步同步高亮。
空棋盘，从第 A 列开始逐列放皇后
1function solveNQueens(n: number): number[] {
2 const queens: number[] = Array(n).fill(-1);
3 const safe = (row: number, col: number): boolean => {
4 for (let c = 0; c < col; c++)
5 if (queens[c] === row ||
6 Math.abs(queens[c] - row) === Math.abs(c - col))
7 return false;
8 return true;
9 };
10 const solve = (col: number): boolean => {
11 if (col === n) return true;
12 for (let row = 0; row < n; row++) {
13 if (safe(row, col)) {
14 queens[col] = row;
15 if (solve(col + 1)) return true;
16 queens[col] = -1;
17 }
18 }
19 return false;
20 };
21 solve(0);
22 return queens;
23}
棋盘4×4
已放皇后-
1 / 32
回溯的本质是深度优先地搜索一棵「决策树」：每一步做一个选择、往下走，走不通就退回换一个选择。剪枝（提前判断冲突、不进注定失败的分支）是它高效的关键——否则就退化成暴力枚举 N^N 种摆法。想枚举所有解，只要在找到一个解后不停下、继续回溯即可。
回溯在哪里用
约束满足：数独、图着色、时间表排布。
组合枚举：全排列、子集、组合、括号生成。
路径搜索：迷宫、单词搜索。凡是「一步步做选择、错了能退回重来」的问题，回溯都适用。
组合枚举：全排列、子集、组合、括号生成。
路径搜索：迷宫、单词搜索。凡是「一步步做选择、错了能退回重来」的问题，回溯都适用。
回溯是搜索类算法的地基——它和动态规划常被对比：DP 用「表」自底向上避免重复子问题，回溯用「递归 + 剪枝」自顶向下地搜索解空间。