09、N皇后

在一行里放一个皇后很容易，难的是：每放一个，都不能与前面已经放好的皇后冲突。N 皇后把回溯中的三件事集中到了一起：做选择、检查约束、撤销选择。

问题与目标

LeetCode 51：N 皇后要求在 n × n 棋盘中放置 n 个皇后，使任意两个皇后不在同一行、同一列或同一条对角线上，返回所有不同的棋盘方案。

例如 n = 4 有两个解，其中一个是：

.Q..
...Q
Q...
..Q.

每个字符串表示一行，Q 是皇后，. 是空位。题目讨论的是列出所有方案，不只是判断有没有解。

把搜索拆成一行一次的选择

如果一次搜索只负责一行，每行最多放一个皇后，“同行冲突”就已经由搜索顺序排除了。此时只需要检查当前列和两种对角线。

用 (row, col) 表示位置：

• 同列的格子 col 相同。
• 左上到右下的对角线，row - col 相同；加上 n - 1 后可作为非负下标。
• 右上到左下的对角线，row + col 相同。

因此，分别用三个标记数组记录列、差值对角线、和值对角线是否已经被占用。候选位置只有在三个标记都为空时才能放置。

一次失败怎样回到上一步

以四阶棋盘为例，第一行先尝试第 0 列。后面的某一行如果找不到合法列，不代表整个问题无解，只表示“第一行这一列与之前选择的组合走不通”。

我们返回上一行，把刚放的 Q 改回 .，并清除它占用的三个标记，再试下一个列位置。撤销操作必须与放置操作一一对应，否则后续分支会继承不属于自己的冲突状态。

当 row == n，说明前 n 行都已放好，保存当前棋盘的一份副本。不能只保存对同一个可变棋盘的引用。

C++17 实现

#include <string>
#include <vector>

class Solution {
 public:
  std::vector<std::vector<std::string>> solveNQueens(int n) {
    if (n <= 0) return {};
    std::vector<std::vector<std::string>> answers;
    std::vector<std::string> board(n, std::string(n, '.'));
    std::vector<bool> columns(n, false);
    std::vector<bool> descending(2 * n - 1, false);
    std::vector<bool> ascending(2 * n - 1, false);
    search(0, n, board, columns, descending, ascending, answers);
    return answers;
  }

 private:
  void search(int row, int n, std::vector<std::string>& board,
              std::vector<bool>& columns, std::vector<bool>& descending,
              std::vector<bool>& ascending,
              std::vector<std::vector<std::string>>& answers) {
    if (row == n) {
      answers.push_back(board);
      return;
    }
    for (int col = 0; col < n; ++col) {
      const int diagonal_a = row - col + n - 1;
      const int diagonal_b = row + col;
      if (columns[col] || descending[diagonal_a] || ascending[diagonal_b]) {
        continue;
      }
      board[row][col] = 'Q';
      columns[col] = descending[diagonal_a] = ascending[diagonal_b] = true;
      search(row + 1, n, board, columns, descending, ascending, answers);
      columns[col] = descending[diagonal_a] = ascending[diagonal_b] = false;
      board[row][col] = '.';
    }
  }
};

复杂度与边界

设实际访问的搜索状态数为 S，解的数量为 K。上面每个非终止状态扫描 n 列，因此时间可写为 O(nS + Kn²)；后一项是复制 K 个棋盘的开销。按不允许重复列的排列上界估算，S = O(n!)，可得宽松上界 O(n·n! + Kn²)，不把输出棋盘的复制时间藏起来。

除答案外，棋盘占 O(n²)，标记和递归栈占 O(n)，合计辅助空间 O(n²)。答案本身占 O(Kn²)。

• n = 1：一个解；n = 2、n = 3：没有解。
• 这里用数组标记避免依赖位宽，未使用位运算优化；不要因为旧摘要提到位运算就把它当成本实现的一部分。
• n <= 0 不在题目正常输入范围内，本实现返回空结果。

做完后应当能讲清

为什么逐行搜索不用记录“行是否占用”？为什么两个对角线分别用和与差？为什么回溯返回后必须清除标记？把这三点讲清，才算真正理解了这道题，而不是记住一个递归模板。