N Queens

N 皇后问题

n−皇后问题是指将 n 个皇后放在 n × n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上

现在给定整数 n，请你输出所有的满足条件的棋子摆法

分析

N 皇后问题要求在 N × N 的棋盘上放置 N 个皇后，使得：

同一行 不能有多个皇后
同一列 不能有多个皇后
同一对角线（主对角线、反对角线） 不能有多个皇后

数组
- col[i] 记录第 i 列是否有皇后
- dg[u - i + n] 记录主对角线 (row - col 相同) 是否有皇后
- udg[u + i] 记录副对角线 (row + col 相同) 是否有皇后
- f[N][N] 存储棋盘布局，初始时全部填充 '.'，放置皇后时填 'Q'
深度优先搜索（DFS）+ 回溯
- u == n：说明 n 行都已放置皇后，找到一个合法方案，输出棋盘
- 否则，尝试在当前行 u 的每一列 i 放置皇后：
  - 若 (i, u) 不冲突，则放置 'Q'，更新 col、dg、udg，递归 dfs(n, u + 1)
  - 回溯（撤销选择），恢复 '.'，取消 col、dg、udg 标记

时间复杂度

最坏情况下，回溯需要遍历所有排列，时间复杂度为 O(N!)

空间复杂度

O(N²) 存储棋盘 f
递归深度最多 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


#include <iostream>

const int N = 20;
bool col[N], dg[N], udg[N]; // 标记列、主对角线、副对角线
char f[N][N]; // 存储棋盘

void dfs(int n, int u)
{
  if (u == n) // 终止条件：成功放置 N 个皇后
  {
    for (int i = 0; i < n; i ++ )
      puts(f[i]); // 输出棋盘
    puts(""); // 额外空行
    return;
  }

  for (int i = 0; i < n; ++ i) // 尝试在当前行 u 的每一列 i 放置皇后
    if (!col[i] && !dg[u - i + n] && !udg[u + i]) // 剪枝，检查列 & 对角线是否可用
    {
      col[i] = dg[u - i + n] = udg[u + i] = true; // 标记皇后占用位置
      f[u][i] = 'Q'; // 放置皇后
      dfs(n, u + 1); // 递归放置下一行
      f[u][i] = '.'; // 回溯：恢复空棋盘
      col[i] = dg[u - i + n] = udg[u + i] = false; // 取消标记
    }
}

int main()
{
  int n;
  std::cin >> n; // 读取 N

  // 初始化棋盘
  for (int i = 0; i < n; ++ i)
    for (int j = 0; j < n; ++ j)
      f[i][j] = '.';

  dfs(n, 0); // 递归搜索

  return 0;
}