hello-algo N 皇后问题全解：回溯算法、对角线剪枝与可视化逐行调试实战

hello-algo 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

导读

N 皇后（n-queens）是回溯算法章节最具代表性的组合优化问题：在n × n棋盘上放置n个皇后，使任意两个皇后不能处于同一行、同一列或同一条斜线。本文以《Hello 算法》（hello-algo）开源仓库中繁中版 N 皇后 PythonTutor 可视化源码文档 为主线，结合 章节正文 与 可运行源码，讲透“逐行放置 + 列/对角线剪枝”的核心策略、cols/diags1/diags2三个布尔数组的设计原理、完整 Python 实现的逐段精读，以及时间/空间复杂度推导。读完你将能够独立实现并可视化任意n皇后的求解程序，并将同一套回溯模板迁移到其他排列类问题。

一、可视化文档在仓库中的定位与关联关系

在 hello-algo 仓库中，chapter_backtracking的每一道例题都配套一份独立的 PythonTutor 可视化文档。这些文档以极简的 Markdown 文件形式存在，其正文内容是一个封装了“完整可运行源码 + 可视化展示参数”的逐行执行链接。本主题对应的关联文档位于：

• zh-hant/codes/pythontutor/chapter_backtracking/n_queens.md（繁中版，本文章核心主体）

从该文件的 URL 载荷可以确认：链接内嵌的是与仓库源码文件逐字一致的n_queens求解程序，可通过逐步执行动画观察每一层递归如何“尝试放置 → 剪枝 → 回溯恢复”。仓库同时维护简体中文版 codes/pythontutor/chapter_backtracking/n_queens.md，以及日文 ja/codes/pythontutor、俄文 ru/codes/pythontutor 等镜像版本，可视化文档仅针对 Python 提供。

与这份可视化文档紧密关联的仓库资源还有两处，构成了完整的“图文 + 可执行代码”学习闭环：

1. 章节正文：zh-hant/docs/chapter_backtracking/n_queens_problem.md。该文档通过src代码块以[file]{n_queens}-[func]{n_queens}的方式将源码文件直接嵌入讲解（见其第 47-49 行），是算法的理论骨架；
2. 可运行源码：zh-hant/codes/python/chapter_backtracking/n_queens.py，即可视化文档所内嵌代码的原始出处。

二、问题定义与回溯建模

先明确问题本身。章节正文的开头给出如下标准表述：

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

当n = 4时，共可以找到两个解。从回溯算法的视角看，n × n棋盘上的n²个格子构成了每一步的全部选择choices；在逐个放置皇后的过程中，棋盘状态不断变化，每个时刻的棋盘即状态state。

这里的关键在于完成“组合问题 → 搜索树”的建模：

• 选择（choices）：当前行可放置皇后的所有列位置col ∈ [0, n)；
• 约束（constraints）：新皇后与已放置皇后不能同行、同列、同对角线；
• 状态（state）：当前棋盘及配套的三个占用标记数组；
• 目标（goal）：递归深度到达最后一行（row == n），说明已成功放置全部n个皇后。

三、三条约束与“逐行放置”剪枝

问题包含三条硬约束：多个皇后不能在同一行、同一列、同一条对角线上。其中对角线又分主对角线\（从左上到右下）与次对角线/（从右上到左下）两种，需分别处理。

由于皇后数量与棋盘行数都为n，可以立刻得到一个重要推论：棋盘每行都允许且只允许放置一个皇后。由此引出“逐行放置策略”：从第 0 行开始，在每行尝试放置一个皇后，直至最后一行结束；一旦某行所有列都无法放置，则回溯到上一行换列重试。

从本质上看，逐行放置策略本身就起到了剪枝作用：它天然杜绝了“同一行出现多个皇后”的全部搜索分支，使暴力枚举量从理论上的C(n², n)组合级，收敛为每层至多n个列选择。需要提醒的是，矩阵起点在左上角，行索引自上而下递增、列索引自左向右递增，这对后续对角线索引公式的理解至关重要。

四、列与对角线剪枝的数据结构设计

要在线性时间内完成“该格子是否可放”的判断，不能每次去扫描已放置的皇后，而应使用三个布尔数组做 O(1) 查询与回溯恢复。

列约束cols：一个长度为n的布尔数组，cols[col] = True表示第col列已有皇后。

对角线约束的索引化是本题的精髓，其数学依据是：

• 主对角线（\）上的所有格子满足row - col为恒定值。即若row₁ - col₁ == row₂ - col₂，则两格必在同一条主对角线上；
• 次对角线（/）上的所有格子满足row + col为恒定值。

进一步推导数组规模：n维方阵中row - col的取值范围是[-n + 1, n - 1]，row + col的取值范围是[0, 2n - 2]，因此主对角线与次对角线各有2n - 1条。在代码实现中，为了让row - col的非负取值能直接作为数组下标，需要加上偏移量n - 1：

• diags1：记录每条主对角线是否已有皇后，下标diag1 = row - col + n - 1，长度2n - 1；
• diags2：记录每条次对角线是否已有皇后，下标diag2 = row + col，长度2n - 1。

五、代码实现逐段精讲

以下代码与可视化文档内嵌程序、仓库源码 n_queens.py 完全一致（含繁中注释原文）：

""" File: n_queens.py Created Time: 2023-04-26 Author: krahets ([e-mail]) """ 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 """Driver Code""" if __name__ == "__main__": n = 4 res = n_queens(n) print(f"輸入棋盤長寬為 {n}") print(f"皇后放置方案共有 {len(res)} 種") for state in res: print("--------------------") for row in state: print(row)

5.1 回溯函数backtrack的四个环节

backtrack严格遵循“记录解 → 遍历选择 → 判断剪枝 → 尝试/递归/回退”的回溯范式：

（1）终止条件（第 18-21 行）：当row == n时表示 0 到n-1行都已成功放好皇后。此时执行res.append([list(row) for row in state])，对state做一次逐行深拷贝后再存入结果。这一步必不可少：state是共享的可变对象，若直接append(state)，后续回溯中的“撤销放置”会破坏已记录的解。

（2）列遍历（第 23 行起）：在当前行遍历所有col。由于采用逐行放置策略，天然规避了行冲突，只需检查列与对角线。

（3）剪枝判断（第 27-28 行）：用not cols[col] and not diags1[diag1] and not diags2[diag2]一次性验证三条件均不冲突，O(1) 完成合法性检查。

（4）尝试与回退（第 29-36 行）：这是回溯的“对称结构”核心：

# 嘗試（遞迴前）：放皇后、打佔用標記 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

递归进入下一行后，无论该分支成功记录解还是因无路可走而返回，都必须执行回退语句，把棋盘格子恢复为"#"、把三个标记恢复为False，从而保证state与标记数组在当前分支上的“干净状态”，供同层后续col复用。这一“先标记、后递归、再还原”的模式正是回溯算法区别于普通 DFS 的关键——它让搜索空间被系统性遍历且不漏解、不重解。

5.2 主函数n_queens的初始化细节

主函数负责搭建回溯所需的全部状态：

• state：n × n的棋盘，全部格子初始化为"#"（空位），放置皇后后改为"Q"；
• cols：长度n的布尔数组；
• diags1/diags2：长度均为2 * n - 1的布尔数组，与第 4 节推导一一对应；
• res：结果容器，类型为list[list[list[str]]]，即“多组方案 × 每组 n 行 × 每行 n 字符”的三层嵌套。

初始化完成后调用backtrack(0, n, state, res, cols, diags1, diags2)从第 0 行开始搜索，最终返回res。

5.3 Driver 代码

n = 4时程序统计并打印解的个数与每张棋盘布局。运行后会得到皇后放置方案共有 2 種，并打印两张棋盘（Q为皇后、#为空位）：

-------------------- ['#', 'Q', '#', '#'] ['#', '#', '#', 'Q'] ['Q', '#', '#', '#'] ['#', '#', 'Q', '#'] -------------------- ['#', '#', 'Q', '#'] ['Q', '#', '#', '#'] ['#', '#', '#', 'Q'] ['#', 'Q', '#', '#']

这与章节正文“当 n = 4 时，共可以找到两个解”的结论完全吻合，可作为实现正确性的最小验证用例。

六、复杂度分析

时间复杂度：逐行放置n次，仅考虑列约束时，从第 0 行到第n-1行分别有n、n-1、…、2、1个选择，搜索树规模上界为n!；每找到一个解，需要复制state矩阵（O(n²)）存入res。因此总体时间复杂度为O(n! · n²)。需要强调的是，对角线约束的剪枝在实际搜索中能大幅缩小搜索空间，因此真实运行效率通常显著优于该上界。

空间复杂度：state占用O(n²)；cols、diags1、diags2各占用O(n)；递归最大深度为n，对应O(n)栈帧。故总空间复杂度为O(n²)。若不把结果容器res计入（其存储的全部解在最坏情况下规模可观），算法运行所需的辅助空间即为上述O(n²)。

七、本地运行与验证方式

仓库为只读代码库，查看与运行按以下步骤进行：

1. 确认环境已安装 Python 3（源码使用类型标注语法，如list[list[str]]，要求 Python 3.9+）；
2. 执行源码文件：

python3 zh-hant/codes/python/chapter_backtracking/n_queens.py

3. 观察输出：先打印棋盘规模与方案总数（应为 2 种），随后以--------------------分隔逐行打印每张棋盘。

若希望逐语句观察递归与回溯过程，可打开可视化文档 zh-hant/codes/pythontutor/chapter_backtracking/n_queens.md，其内嵌链接预置了完整源码与逐步执行参数（如cumulative=false、Python 3.11 解释器），可精确看到“尝试放置 → 剪枝失败跳列 → 回溯恢复”在每个栈帧上的数据变化。

八、同类问题与多语言扩展

回溯算法在本仓库的chapter_backtracking中是一套统一方法论。将本题的“多选择 + 多约束 + 尝试/回退”框架与以下配套可视化文档对照学习，可以快速掌握排列类、子集类问题的变体：

• 全排列去重：permutations_i.md、permutations_ii.md（引入selected选择标记与相等元素剪枝）；
• 子集和问题：subset_sum_i.md、subset_sum_ii.md（引入排序 + 重复剪枝）。

对比可见：全排列用一维state记录排列、selected标记元素是否被选；子集和用target - choice累计约束；而 N 皇后用二维棋盘作为state、三个一维布尔数组承载冲突检测。“状态表示 + 剪枝条件”因题而异，但“尝试 → 递归 → 回退”的骨架始终不变，这正是回溯一章最值得提炼的可复用思想。

同一算法在仓库中还提供多种主流语言的等价实现（位于各自语言的chapter_backtracking/n_queens.*），例如 C 版、C++ 版、Java 版 与 Go 版，命名与逻辑保持一致，便于跨语言对照阅读与本地编译执行。

【免费下载链接】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