《Hello 算法》n 皇后问题深度解析：回溯框架下的逐行放置与列、对角线三重剪枝-育师

《Hello 算法》n 皇后问题深度解析：回溯框架下的逐行放置与列、对角线三重剪枝

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文围绕开源数据结构与算法教程《Hello 算法》中「n 皇后问题」一节（见俄文原文及简体中文对应章节）展开，结合仓库内 Python、Java、C、Go 等语言的真实源码实现，系统讲解如何用回溯算法在n × n棋盘上放置n个互不攻击的皇后。读完本文，你将掌握「逐行放置 + 列剪枝 + 主/次对角线剪枝」这一经典回溯解法，理解row - col与row + col两个坐标恒等式的几何本质，并能直接运行仓库中的多语言示例验证结果。

n 皇后问题是回溯算法最经典的训练题目之一：它同时具备清晰的解空间（n × n个格子）、三条硬性约束（同行、同列、同对角线）以及由剪枝带来的巨大性能差异。《Hello 算法》在回溯算法章节介绍完"尝试与回退"（try & backtrack）思想后，用本问题演示约束如何被翻译成可高效判定的数据结构。

问题定义：如何才算"互不攻击"

!!! question

按照国际象棋规则，皇后可以攻击同一行、同一列或同一对角线上的任意棋子。给定 `n` 个皇后与一块 `n × n` 的棋盘，请找出所有这样的放置方案：任意两个皇后都无法互相攻击。

当n = 4时共有两个解（见下图）。从回溯算法的视角看，n × n棋盘上的n^2个格子构成所有可用的choices（选择）；随着皇后被逐个放置，棋盘内容（即状态state）不断变化，因此棋盘当前的样子就是算法的状态。

该问题共有三条约束，图中分别用不同颜色标出：任意两个皇后不能位于同一行、同一列或同一条对角线上。注意对角线分两类：主对角线方向为\，次对角线方向为/。

明确问题的数学模型

在动手编码前，先把它翻译成回溯算法的三个要素：

选择（choices）：每个待放置皇后可选的落点，共n^2个格子；
约束（constraints）：落点不能与已放皇后的行、列、主对角线、次对角线冲突；
状态（state）：当前棋盘的放置情况。

这样，问题就变成"依次为每个皇后做选择、每步用约束剪枝、全部放完即记录一解"的标准回溯流程，与仓库源码中 Python 实现的state、cols、diags1、diags2等变量一一对应。

逐行放置策略：一种天然的剪枝

皇后数与棋盘行数相等，都为n，因此可以立刻得到一个关键结论：棋盘的每一行恰好且必须放置一个皇后。

由此得到"逐行放置"策略：从第 1 行开始，每行放置一个皇后，直至第n行放完。下图展示了n = 4时逐行放置的搜索过程（受篇幅所限只绘制了第 1 行出发的一条分支，凡是不满足列与对角线约束的尝试均被剪除）。

从本质上说，逐行放置策略本身就构成了一次剪枝：它把"同一行出现多个皇后"的所有分支预先排除，使搜索树的分支数从一开始就由"列数 × 行数"收缩为单纯的列选择。

用三个布尔数组实现三重剪枝

列约束：cols 数组

为满足"同列不冲突"，使用长度为n的布尔数组cols记录每一列是否已存在皇后。每次放置前，用cols剪去已被占用的列；回溯（撤销放置）时同步更新cols的状态。

!!! tip "坐标系约定"

矩阵的坐标原点在左上角：行索引自上而下增大，列索引自左向右增大。后面所有 `row`、`col` 的下标计算均遵循此约定。

对角线约束的数学本质：两个恒定值

对角线约束需要一点巧思。设某格子坐标为(row, col)：

在同一主对角线（方向\）上的所有格子，row - col的值恒定。换言之，只要两格满足row₁ - col₁ = row₂ - col₂，它们必在同一条主对角线上；
在同一次对角线（方向/）上的所有格子，row + col的值恒定。

于是主对角线可用数组diags1标记，次对角线用diags2标记，放置皇后时只需检查两个布尔值即可：

这里容易犯的一个错误是：用布尔值无法区分棋盘上两条数值相同但分属不同对角线的斜线。row - col只能区分主对角线、row + col只能区分次对角线，二者不可混用——这正是需要两个独立数组diags1、diags2的原因。

代码实现：Python 完整示例

棋盘是n × n方阵，因此row - col的取值范围是[-n + 1, n - 1]，row + col的取值范围是[0, 2n - 2]。这说明主、次对角线各有2n - 1条，所以diags1与diags2的长度都取2n - 1。为了让负数下标归零，实际计算主对角线编号时统一做了偏移：

# 该格子对应的主对角线和次对角线编号 diag1 = row - col + n - 1 diag2 = row + col

下面是以 codes/python/chapter_backtracking/n_queens.py 为蓝本的完整求解函数。棋盘用字符矩阵表示，"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(r) for r 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

代码中backtrack清晰呈现了回溯的四个标准动作：判断终止 → 遍历选择 → 尝试并递归 → 回退撤销。其中"尝试"通过state/cols/diags1/diags2的同时置位完成，而"回退"则是对称地复位，保证同一数组在兄弟分支间共享且状态正确——这正是回溯算法区别于普通深搜的关键所在。

多语言对照与一键运行验证

该问题在仓库中提供了全系列语言实现，逻辑与上文 Python 版本完全同构：

静态类型版可对比 Java 实现（nQueens返回List<List<List<String>>>）；
内存敏感场景可参考 C 实现（用char矩阵与动态分配的res，并在main末尾free释放）；
其余见 C++、Go、C#、JS、TS、Rust、Swift、Dart、Kotlin、Ruby 等目录。

直接运行 Python 版即可看到结果：

python3 codes/python/chapter_backtracking/n_queens.py

仓库中各语言文件均带有Driver Code（如 Python 版取n = 4），运行输出会打印"皇后放置方案共有 2 种"，随后逐个打印两组 4 × 4 解，恰好对应开头示意图中的两个解。Go 语言还额外提供了单元测试 n_queens_test.go，通过TestNQueens在go test下对n = 4的求解过程做可重复验证。

复杂度分析

时间复杂度

由于逐行放置n个皇后，且列约束进一步将每行的候选从n压缩为依次递减的数量，从第 1 行到最后一行可用的列数分别为n, n-1, …, 2, 1，因此搜索规模约为O(n!)；而每次得到一个解时，需要深拷贝state矩阵并放入res，拷贝耗时O(n²)。故总时间复杂度上界为O(n! · n²)。在实际运行中，对角线约束的剪枝还会大幅压缩搜索空间，因此真实效率通常优于该理论界。

空间复杂度