Hello 算法：用回溯与对角线索引解决 N 皇后问题

本文基于 hello-algo 仓库中“回溯算法”章节的 n 皇后问题文档，完整讲解 N 皇后问题的建模思路：逐行放置策略如何天然剪枝、如何利用 row - col 与 row + col 的恒定值规律把对角线约束压缩为线性数组查询，并给出多语言可运行的回溯实现、时间/空间复杂度推导与剪枝验证测试。读完后你将掌握“约束条件 → 剪枝结构”这一回溯问题的通用设计方法，并能独立实现、调试 N 皇后求解器。

问题定义与解空间

根据国际象棋的规则，皇后可以攻击与同处一行、一列或一条斜线上的棋子。给定 $n$ 个皇后和一个 $n \times n$ 大小的棋盘，目标是寻找使得所有皇后之间无法相互攻击的摆放方案。

当 $n = 4$ 时，共可以找到两个解：

从回溯算法的角度看，$n \times n$ 大小的棋盘共有 $n^2$ 个格子，这就是所有的选择 choices；在逐个放置皇后的过程中，棋盘状态在不断地变化，每个时刻的棋盘就是状态 state。

下图展示了本题的三个约束条件：多个皇后不能在同一行、同一列、同一条对角线上。值得注意的是，对角线分为主对角线 \ 和次对角线 / 两种：

逐行放置策略：行约束的“结构性剪枝”

皇后的数量和棋盘的行数都为 $n$，因此容易得到一个推论：棋盘每行都允许且只允许放置一个皇后。

也就是说，可以采取逐行放置策略：从第一行开始，在每行放置一个皇后，直至最后一行结束。下图所示为 4 皇后问题的逐行放置过程，受画幅限制仅展开了第一行的其中一个搜索分支，并且将不满足列约束和对角线约束的方案都进行了剪枝：

从本质上看，逐行放置策略起到了剪枝的作用：它避免了同一行出现多个皇后的所有搜索分支，等于在遍历解空间之前就把行约束“吸收”进了搜索结构本身。这也解释了为什么实现中递归函数的参数只有 row 而没有 col——列是在循环中枚举的，行则由递归深度决定。

这一策略同时决定了搜索树的宽度：从第一行到最后一行分别有 $n$、$n-1$、$\dots$、$2$、$1$ 个候选列（考虑列约束后），因此总的时间开销约为 $O(n!)$。

列与对角线剪枝：约束的线性化表示

如果每次判断新皇后是否合法都要扫描整个棋盘，检查代价会退化为 $O(n)$，搜索效率显著下降。hello-algo 的实现做法是：在回溯中动态维护三个布尔数组，把合法性检查降为 $O(1)$。

列约束：cols 数组

为了满足列约束，利用一个长度为 $n$ 的布尔型数组 cols 记录每一列是否有皇后。在每次决定放置前，通过 cols 将已有皇后的列进行剪枝，并在回溯中动态更新 cols 的状态。

请注意，矩阵的起点位于左上角，其中行索引从上到下增加，列索引从左到右增加。

主对角线：row - col 恒定

那么，如何处理对角线约束呢？设棋盘中某个格子的行列索引为 $(row, col)$，选定矩阵中的某条主对角线，会发现该对角线上所有格子的行索引减列索引都相等，即主对角线上所有格子的 $row - col$ 为恒定值。

也就是说，如果两个格子满足 $row_1 - col_1 = row_2 - col_2$，则它们一定处在同一条主对角线上。利用该规律，可以借助数组 diags1 记录每条主对角线上是否有皇后。

次对角线：row + col 恒定

同理，次对角线上的所有格子的 $row + col$ 是恒定值。同样可以借助数组 diags2 来处理次对角线约束：

数组下标与长度推导

需要注意，$n$ 维方阵中 $row - col$ 的范围是 $[-n + 1, n - 1]$，$row + col$ 的范围是 $[0, 2n - 2]$，所以主对角线和次对角线的数量都为 $2n - 1$，即数组 diags1 和 diags2 的长度都为 $2n - 1$。

由于 $row-col$ 可能为负数，代码中需要加上偏移量 $n-1$ 把下标平移到非负区间。在 n_queens.py 中这一映射体现为：

# 计算该格子对应的主对角线和次对角线
diag1 = row - col + n - 1   # 主对角线，偏移 n-1 消除负下标
diag2 = row + col           # 次对角线，无需偏移

C++ 版本 n_queens.cpp 中的写法完全一致：

int diag1 = row - col + n - 1;
int diag2 = row + col;

这个“约束 → 数组下标”的映射是本题最值得记住的技巧：凡是能被某个线性表达式唯一标识的结构（列、对角线），都可以用一个哈希式布尔数组做 $O(1)$ 占用判断，而不必扫描棋盘。

完整代码实现：尝试、递归、回退

下面以 Python 实现 为主，结合仓库中的 Java 与 C++ 版本对照讲解核心结构。

def backtrack(
    row: int, n: int, state: list[list[str]], res: list[list[list[str]]],
    cols: list[bool], diags1: list[bool], diags2: list[bool],
):
    """回溯算法：n 皇后"""
    # 当放置完所有行时，记录解
    if row == n:
        res.append([list(row) for row in state])
        return
    # 遍历所有列
    for col in range(n):
        # 计算该格子对应的主对角线和次对角线
        diag1 = row - col + n - 1
        diag2 = row + col
        # 剪枝：不允许该格子所在列、主对角线、次对角线上存在皇后
        if not cols[col] and not diags1[diag1] and not diags2[diag2]:
            # 尝试：将皇后放置在该格子
            state[row][col] = "Q"
            cols[col] = diags1[diag1] = diags2[diag2] = True
            # 放置下一行
            backtrack(row + 1, n, state, res, cols, diags1, diags2)
            # 回退：将该格子恢复为空位
            state[row][col] = "#"
            cols[col] = diags1[diag1] = diags2[diag2] = False


def n_queens(n: int) -> list[list[list[str]]]:
    """求解 n 皇后"""
    # 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
    state = [["#" for _ in range(n)] for _ in range(n)]
    cols = [False] * n           # 记录列是否有皇后
    diags1 = [False] * (2 * n - 1)  # 记录主对角线上是否有皇后
    diags2 = [False] * (2 * n - 1)  # 记录次对角线上是否有皇后
    res = []
    backtrack(0, n, state, res, cols, diags1, diags2)

    return res

代码结构可以拆成四个要点：

1. 终止条件与解的记录：row == n 表示所有行都已放置，此时把 state 的深拷贝（Python 中为 [list(row) for row in state]，Java 中为逐行 new ArrayList<>(sRow) 的复制）加入 res。因为 state 在后续回退中会被反复改写，若直接存入引用，所有解最终都会退化成同一块被修改后的棋盘。这一点在 n_queens.java 中体现得尤为明确：copyState 是逐行新建列表后 res.add(copyState)。
2. 剪枝判断：cols[col]、diags1[diag1]、diags2[diag2] 三者全为 False 才允许放置，一次判断即覆盖列与两种对角线约束。
3. 尝试与递归：写入 state[row][col] = "Q" 并置位三个布尔数组，然后递归处理 row + 1。
4. 回退：递归返回后，把格子恢复为 "#" 并把三个数组对应位置复位，保证同层的下一个 col 分支看到的是干净的搜索状态。这与本仓库 回溯算法章节 中“尝试与回退互为逆向操作”的通用描述完全对应。

各语言实现的文件位置如下，逻辑均保持一致：

语言	实现文件
Python	n_queens.py
Java	n_queens.java
C++	n_queens.cpp
C	n_queens.c
Go	n_queens.go
TypeScript	n_queens.ts
Rust	n_queens.rs

Go 语言版本附带了一个可执行的验证入口 n_queens_test.go：

func TestNQueens(t *testing.T) {
	n := 4
	res := nQueens(n)

	fmt.Println("输入棋盘长宽为 ", n)
	fmt.Println("皇后放置方案共有 ", len(res), " 种")
	for _, state := range res {
		fmt.Println("--------------------")
		for _, row := range state {
			fmt.Println(row)
		}
	}
}

Python 的驱动代码（__main__ 部分）与其一致：输入 n = 4，运行后应输出“皇后放置方案共有 2 种”，并逐行打印两个解的棋盘——这正是文档开头 $n = 4$ 图示的解。可以直接用 python codes/python/chapter_backtracking/n_queens.py 运行验证，Go 版则可用 go test ./codes/go/chapter_backtracking/ -run TestNQueens 运行。

复杂度分析

文档给出的推导与代码实现严格对应：

• 时间复杂度 $O(n! \cdot n^2)$：逐行放置 $n$ 次，考虑列约束后，从第一行到最后一行分别有 $n$、$n-1$、$\dots$、$2$、$1$ 个选择，搜索本身使用 $O(n!)$ 时间；当记录解时，需要复制矩阵 state 并添加进 res，复制操作使用 $O(n^2)$ 时间。因此总体时间复杂度为 $O(n! \cdot n^2)$。实际上，根据对角线约束的剪枝也能大幅缩小搜索空间，因而搜索效率往往优于以上时间复杂度上界。
• 空间复杂度 $O(n^2)$：数组 state 使用 $O(n^2)$ 空间；数组 cols、diags1 和 diags2 皆使用 $O(n)$ 空间；最大递归深度为 $n$，使用 $O(n)$ 栈帧空间。综合下来空间复杂度为 $O(n^2)$。

需要说明的是，$O(n! \cdot n^2)$ 中 $n^2$ 因子来自“记录解时复制棋盘”。如果只需输出解而不保留全部棋盘的副本（例如直接在解位置打印），这部分开销可以省掉，但仓库中的实现选择保留完整棋盘快照，便于统一地返回所有解，这也是 Java、C++ 等多语言版本一致的做法。

小结与练习延伸

N 皇后问题把回溯算法的三要素体现得非常完整：

1. 选择空间：每行的 $n$ 个格子；
2. 约束剪枝：逐行放置吸收行约束，cols / diags1 / diags2 三个布尔数组把列与对角线约束变成 $O(1)$ 判断；
3. 尝试与回退：置位数组并递归，递归返回后把 state 与三个数组同步复位。

其中“对角线 → 线性索引”的映射（$row - col + n - 1$ 与 $row + col$）是可迁移到更一般搜索问题上的技巧：先为约束结构找到一个唯一的线性标识，再用数组做占用表，就能避免每次扫描。

如果想进一步练习，可以阅读同章节的 回溯算法总论、全排列问题 与 子集和问题，以及 练习题 中“下一枚皇后可以放在哪些位置”一题——它要求手工推演第 2 行的剪枝过程（已知皇后在 (0, 1) 和 (1, 3) 时，第 2 行仅剩 (2, 0) 可尝试），是检验本文剪枝规则理解深度的好检验。