《Hello 算法》N 皇后问题：回溯搜索框架与列、对角线剪枝的多语言实现剖析

本文以英文版文档 n_queens_problem.md 为核心，系统讲解经典 N 皇后问题在回溯算法框架下的建模过程：如何将“棋盘状态”抽象为 state、将“可放置的格子”抽象为 choices，并通过逐行放置策略与 cols / diags1 / diags2 三组布尔数组完成剪枝。仓库源码覆盖 Python、Java、C、C++、Go、Rust、Swift 等 14 种语言，读者可对照阅读任一语言的 n_queens 实现，掌握一套可迁移到排列、子集和等回溯问题的通用解法。

一、问题定义：一个状态、选择与约束清晰的标准回溯案例

按照国际象棋规则，皇后可以攻击同一行、同一列以及同一条对角线上的任意棋子。给定 $n$ 个皇后和一个 $n \times n$ 棋盘，N 皇后问题要求找出一组摆放方案，使得任意两个皇后都无法互相攻击。

如图中所示，当 $n = 4$ 时一共可以找到 2 个可行解。从回溯算法的视角看，$n \times n$ 的棋盘共有 $n^2$ 个格子，这些格子提供了全部的选择 choices；而在逐个放置皇后的过程中，棋盘状态不断变化，每一时刻的棋盘即对应着回溯框架中的状态 state。

N 皇后问题之所以适合作为回溯算法的入门案例，正是因为它天然具备了回溯搜索的三个要素：

回溯三要素	在本问题中的映射
choices（选择）	当前行所有未冲突的列位置
state（状态）	当前已部分放置皇后的棋盘
约束（constraint）	任意两皇后不同行、不同列、不同对角线

对该问题更一般的回溯方法论（状态空间树、剪枝、尝试与回退），可参见同章节的 backtracking_algorithm.md。

二、三类几何约束与逐行放置策略

下图展示了该问题的三类核心约束：多个皇后不能处于同一行、同一列或同一条对角线。需要特别注意的是，对角线分为两类——主对角线 \ 与副对角线 /。

逐行放置：一行一皇后的必然推论

由于皇后的数量与棋盘行数都是 $n$，可以推出一个重要结论：棋盘每一行有且只能放置一个皇后。

这意味着可以采用逐行放置策略：从第 1 行开始，在每一行放置一个皇后，直到最后一行也放置完毕。下图展示了 4 皇后问题逐行放置的搜索过程（图中仅展开了第 1 行的一个搜索分支，所有违反列约束或对角线约束的方案均被剪枝）：

从本质上讲，逐行放置策略本身就起到剪枝作用——它直接避开了“同一行出现多个皇后”这一整类非法搜索分支，把问题从“在 $n^2$ 个格子中选 $n$ 个”压缩为“每一行在 $n$ 个列中选 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 处理副对角线的约束。

下图直观展示了上述三种编码方式：cols 逐列记录占用情况，diags1 / diags2 分别按 $row - col$ 与 $row + col$ 的取值记录主、副对角线的占用情况。

数组长度推导：为什么是 $2n - 1$

在 $n \times n$ 方阵中：

• $row - col$ 的取值范围是 $[-n + 1, n - 1]$；
• $row + col$ 的取值范围是 $[0, 2n - 2]$。

因此主对角线与副对角线的数量均为 $2n - 1$，即 diags1 与 diags2 两个数组的长度都是 $2n - 1$。由于数组下标不能为负，实际代码中会通过 diag1 = row - col + n - 1 将主对角线索引统一平移到 $[0, 2n - 2]$（见下文代码实现）。

四、多语言代码实现与逐行解读

Python 完整实现

以下是仓库中 python 版实现 的完整代码，其中 # 表示空格、Q 表示皇后：

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 深拷贝后加入结果集 res。注意 Python 中需要 [list(row) for row in state] 逐行复制，避免后续回退修改污染已记录的解。
2. 状态压缩（尝试）：diag1 = row - col + n - 1 把主对角线差 row - col 平移到非负下标；diag2 = row + col 直接作为副对角线下标。
3. 剪枝判断：只有当 cols[col]、diags1[diag1]、diags2[diag2] 全部为 False（即列、主对角线、副对角线上均无皇后）时，才允许放置。
4. 递归下探：放置当前行的皇后后，递归进入 backtrack(row + 1, ...)，实现“逐行放置”。
5. 回退还原：递归返回后，将格子恢复为 #，并把三个约束标记还原为 False，以释放该位置供后续分支尝试。

其他语言实现的共性观察

同一逻辑在仓库中以高度一致的形态覆盖了全部主流语言，均可对照阅读：

• Java 实现：使用 List<List<String>> 表示棋盘，backtrack(int row, int n, ...) 签名与 Python 版完全同构，入口函数 nQueens(int n) 内初始化 state、cols、diags1、diags2 后从第 0 行开始递归。
• Go 实现：除求解代码外，仓库还提供了配套的 n_queens_test.go 测试文件，以 n = 4 为例断言可求得解并打印结果，可直接验证算法正确性。
• C 实现：由于语言本身缺少动态数组设施，C 版将棋盘与结果均声明为 char state[MAX_SIZE][MAX_SIZE] / char ***res（其中 MAX_SIZE = 100），并利用 strcpy 深拷贝行字符串、手动 malloc / free 管理结果内存——这从源码结构上反映了同样算法在不同内存模型下的落地差异，也提示在实际应用中需要关注棋盘规模上限。

其余语言实现分别位于 C++、C#、Dart、JavaScript、Kotlin、Ruby、Rust、Swift、TypeScript。

运行与验证输出

Python 文件自带的 Driver Code 以 $n = 4$ 调用 n_queens(4)，并打印解的数量与每个棋盘布局。运行：

python3 n_queens.py   # 在 en/codes/python/chapter_backtracking/ 目录下

预期输出两个解（对应图中两种摆放）：

Input chessboard size is 4
There are 2 queen placement solutions
--------------------
['#', 'Q', '#', '#']
['#', '#', '#', 'Q']
['Q', '#', '#', '#']
['#', '#', 'Q', '#']
--------------------
['#', '#', 'Q', '#']
['Q', '#', '#', '#']
['#', '#', '#', 'Q']
['#', 'Q', '#', '#']

需要说明的是：示例驱动代码中的 # 与 Q 正是对“空位”与“皇后”两种棋盘状态的可视化编码，四个 Q 之间既不同行也不同列、不同对角线。

五、复杂度分析：$O(n! \cdot n^2)$ 时间与 $O(n^2)$ 空间

时间复杂度

逐行放置 $n$ 个皇后时，若只考虑列约束，从第 1 行到第 $n$ 行可供选择的列数分别为 $n, n-1, \dots, 2, 1$，对应 $O(n!)$ 的排列量级。而在记录一个解时，需要复制矩阵 state 并加入 res，该复制操作消耗 $O(n^2)$ 时间。因此：

$$\text{总时间复杂度} = O(n! \cdot n^2)$$

值得强调的是，实际执行中对角线约束的剪枝会显著缩小搜索空间，因此真实搜索效率通常优于上述最坏时间复杂度所暗示的水平。作为佐证，4 皇后在穷举所有排列时需要检查 $4! = 24$ 个候选，而实际求得解只有 2 个——绝大多数分支都在第 2、3 行即被对角线剪枝提前终止。

空间复杂度

• 棋盘数组 state 占用 $O(n^2)$ 空间；
• 数组 cols、diags1、diags2 各占用 $O(n)$ 空间；
• 最大递归深度为 $n$，函数调用栈占用 $O(n)$ 空间。

三者相加，整体空间复杂度为 $O(n^2)$（由棋盘本身的存储主导）。

六、延伸阅读：与同章节回溯例题的对比

N 皇后问题并非孤例，仓库的 chapter_backtracking 目录还收录了两类与之同框架的经典回溯问题，适合对比研读，以提炼“状态 + 选择 + 剪枝”的普适套路：

• 排列问题 permutations_problem.md：用 selected 数组记录元素是否被选，对应 N 皇后中的 cols 角色，并额外演示了如何用哈希集合去除重复排列；
• 子集和问题 subset_sum_problem.md：展示了“元素可重复选取 / 结果去重”两类变体的剪枝写法。

三者共同构成了回溯算法的典型场景矩阵：排列型（关注元素顺序）、组合型（关注子集构成）与棋盘/布局型（关注几何约束的编码）。

七、小结

N 皇后问题的价值在于它把抽象的几何约束转化为简洁的数组编码，示范了回溯算法的完整闭环——逐行放置缩小选择空间、cols/diags1/diags2 三数组提供 $O(1)$ 剪枝判断、递归记录解、回退还原状态。其中“用数学恒等式（差、和）为不可枚举的对角线建立索引”的思想，可以迁移到八数码、数独、图着色等大量约束满足类问题中。结合 backtracking_algorithm.md 的框架讲解与 summary.md 的章节总结，即可完成从例题到方法论的系统化学习。