N 皇后（回溯）

N 皇后问题：在 N × N 的棋盘上放置 N 个皇后，使任意两个不在同一行、同一列、同一对角线。求所有的合法摆放方案。

这是回溯算法 (Backtracking) 的代表题。

回溯 = 深度优先 + 撤销

回溯的本质是 DFS + 反悔机制：

1. 尝试一种选择（往状态里加东西）
2. 递归到下一层去解决子问题
3. 递归回来后撤销刚才的选择（恢复状态）
4. 继续尝试下一种选择

代码骨架：

void solve(状态 s) {
  if (s 是完整解) { 收集; return; }
  for (每种可能的选择 c) {
    if (c 合法) {
      做选择(c);
      solve(s');
      撤销选择(c);   // ← 回溯的灵魂
    }
  }
}

N 皇后的状态设计

逐行放皇后 —— 第 row 行选一列 c，往第 row+1 行递归。判断 (row, c) 是否合法只需检查：

• 列：之前哪几列已被占？维护 usedCol[c]
• ↘ 对角线（左上到右下）：row - col 相同 → 用 r - c + (n-1) 当下标，usedD1
• ↙ 反对角线（右上到左下）：row + col 相同 → usedD2

每次”做选择”就把这三个标记设 true，撤销时设回 false。所有判断 O(1)。

解的数量

8 皇后的 92 个解是这个题的传统起点，但视觉上 5、6、7 更适合演示 —— 步数适中，且解数有明显差异。

复杂度

• 时间：最坏 O(n!)，但合理剪枝下远小于 n!（实测 8 皇后只搜约 2k 步）
• 空间：O(n) 递归栈 + 标记数组

在动画里看什么

• 浅淡的棋盘斜线 hash 是默认配色
• 蓝色高亮 + 圆点：当前正在尝试放置的格子
• 绿色高亮：上一帧放下了皇后
• 暖红色高亮：因冲突拒绝
• 浅红覆盖：当前位置如果放下，会攻击到的其他格（行 / 列 / 对角线）
• ♛ 字符：已放下的皇后
• 下方实时显示已找到的解的个数和列编码

注意撤销 (backtrack) 时整行的皇后消失 —— 那一帧最能看到”反悔”动作。