N Queens

51. N皇后

分析

棋盘表示：
- 使用一个长度为 n 的字符串数组 path 表示棋盘，每个字符串表示棋盘的一行，'.' 表示空格，'Q’ 表示皇后
- res 保存所有可能的棋盘方案
冲突检测：
- 使用三个布尔数组记录皇后占据的列和对角线：
  - col[i] 表示第 i 列是否有皇后
  - dg[i] 表示正对角线是否有皇后（从左上到右下，索引为 u - i + n）
    - 正对角线元素使用索引u - i来表示，因为正对角线上的元素都满足坐标x - y == 0
    - 棋盘上所有元素坐标之差范围是-(n - 1) ~ n - 1，加偏移量 n 将其映射为1 ~ 2n - 1
  - udg[i] 表示反对角线是否有皇后（从右上到左下，索引为 u + i）
    - 反对角线元素使用u + i来表示，因为反对角线上的元素都满足坐标x + y == n
    - 棋盘上所有元素坐标之和范围为0 ~ 2(n - 1)，因此不需要加偏移量
回溯放置皇后：
- 从第 u 行开始，尝试在每一列放置皇后
- 如果当前列、正对角线、反对角线均未被占用，则将皇后放置在对应位置，并标记这些区域为占用
- 递归尝试放置下一行的皇后
- 回溯时，将皇后移除，并恢复状态
结果保存：
- 当递归到最后一行 u == n 时，说明当前方案有效，将棋盘方案保存到结果中

时间复杂度

每一行最多有 n 个选择，搜索深度为 n，回溯过程的总时间复杂度约为 O(n!)

空间复杂度

需要存储棋盘状态 path 和标记数组（col、dg、udg），每个的大小为 O(n)

总空间复杂度为 O(n²)，主要用于存储结果

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


class Solution
{
public:
    std::vector<std::vector<std::string>> res; // 存储所有有效的棋盘方案
    std::vector<std::string> path; // 当前棋盘状态
    std::vector<bool> col, dg, udg; // 列、正对角线、反对角线的占用状态

    vector<vector<string>> solveNQueens(int n)
    {
      // 初始化棋盘和标记数组
      path = std::vector<std::string>(n, std::string(n, '.'));
      col = std::vector<bool>(n);
      dg = std::vector<bool>(2 * n);
      udg = std::vector<bool>(2 * n);

      // 开始回溯
      dfs(n, 0);
      return res;
    }

    void dfs(int n, int u)
    {
      // 如果所有行都放置完成，保存当前棋盘方案
      if (u == n)
      {
        res.push_back(path);
        return;
      }

      // 遍历当前行的每一列，尝试放置皇后
      for (int i = 0; i < n; ++i)
      {
        if (!col[i] && !dg[u - i + n] && !udg[u + i]) // 检查是否冲突
        {
          // 放置皇后并标记状态
          col[i] = dg[u - i + n] = udg[u + i] = true;
          path[u][i] = 'Q';

          // 递归放置下一行
          dfs(n, u + 1);

          // 回溯：移除皇后并恢复状态
          path[u][i] = '.';
          col[i] = dg[u - i + n] = udg[u + i] = false;
        }
      }
    }
};