当前位置：首页 > news >正文

N皇后问题：从回溯算法到状态压缩的深度解析与优化实践

news 2026/8/2 17:19:51

1. 问题引入：从棋盘到代码的经典回溯

如果你对算法竞赛或者数据结构与算法这门课稍有接触，那么“N皇后问题”这个名字你一定不陌生。它就像一个算法领域的“Hello World”，但远比打印一行文字要复杂和深刻得多。我第一次在SCAU（华南农业大学）的OJ（Online Judge）系统上看到这道编号为18124的题目时，心里想的是：“哦，经典回溯，应该不难。”但真正动手去实现一个高效、优雅且能通过所有测试用例的解时，才发现里面藏着不少门道。

N皇后问题的描述非常直观：在一个N×N的国际象棋棋盘上，摆放N个皇后，使得它们彼此之间不能相互攻击。皇后在国际象棋里可以横着走、竖着走、斜着走，不限格数。所以，问题的约束就变成了：任意两个皇后不能在同一行、同一列、同一主对角线（左上到右下）或同一副对角线（右上到左下）上。

这个问题之所以经典，是因为它完美地契合了“回溯算法”的教学场景。回溯的本质就是一种“试错”思想：我们尝试在棋盘上一步步放置皇后，如果当前放置导致后续无法满足条件（即冲突），就撤销这一步（回溯），尝试下一个位置。它像一棵决策树的深度优先搜索，我们遍历所有可能的摆放路径，并剪掉那些明显不可能通向最终答案的枝条（剪枝）。

今天，我们就以SCAU OJ 18124这道题为例，不单单是给出一个能AC（Accept，通过）的代码，而是深入探讨如何从最朴素的暴力搜索开始，一步步通过优化策略，写出一个在时间和空间上都表现优异的解。我们会聊到如何表示棋盘状态、如何进行高效的冲突检测、有哪些关键的剪枝技巧，以及如何将思路清晰地转化为代码。无论你是正在备战算法考试的新手，还是想重温回溯算法精髓的老手，相信这篇详细的拆解都能给你带来收获。

2. 问题建模与状态表示：如何为棋盘“编码”

动手写代码之前，我们必须先把问题“翻译”成计算机能处理的数据结构。这一步的选择，直接决定了后续算法的效率和实现的复杂度。

2.1 最直观的表示：二维数组

我们最先想到的可能是用一个N x N的二维数组（比如int board[N][N]）来表示棋盘。用1表示放置了皇后，0表示空位。这种表示法非常符合人类的视觉直觉，检查冲突时，我们需要扫描当前皇后的行、列和两条对角线，看看是否有其他1。对于每个位置，检查冲突的时间复杂度是 O(N)。在回溯过程中，我们需要频繁地设置和清除某个位置的状态（放置皇后和移走皇后）。

为什么这种表示法在N较大时效率不高？主要问题在于冲突检测的成本。每次尝试放置一个皇后，我们都需要扫描它所在的行、列和两条对角线，这最多涉及大约4N个格子的检查。虽然对于小N（比如N<=10）问题不大，但当N变大时，这个常数因子会变得可观。更重要的是，这种表示法没有利用到问题的一个关键特性：我们必然在每一行放一个皇后。因为如果有两行都没放皇后，那么至少有一行会放两个，这显然不可能。所以，我们其实不需要记录整个棋盘，只需要记录每一行的皇后放在了哪一列。

2.2 更高效的表示：一维数组（列位置记录）

这是解决N皇后问题最常用、最高效的表示方法。我们定义一个长度为N的一维数组cols。

cols[i] = j的含义是：第 i 行的皇后，放置在第 j 列。
这里i和j的范围都是[0, N-1]。

这种表示法自动满足了“每一行只有一个皇后”的约束。现在，我们的搜索空间从N^2个格子缩小到了每一行有N种列选择，总状态数为N^N（当然，回溯会剪掉绝大部分）。我们的任务变成了：为cols[0], cols[1], ..., cols[N-1]这N个变量，在[0, N-1]中寻找一个赋值，使得它们满足列和对角线的约束。

那么，冲突检测如何做呢？假设我们当前想要在第row行放置一个皇后，尝试放在第col列。我们需要检查这个(row, col)位置是否与之前已经放置好的皇后（即第0行到第row-1行）冲突。

列冲突：检查是否有任何已放置的皇后i，满足cols[i] == col。即是否有其他行的皇后也放在了第col列。
主对角线冲突（左上-右下）：在同一条主对角线上的格子，其行号 - 列号的值是相等的。例如，(1,1), (2,2), (3,3) 的row - col都等于0。所以我们需要检查是否有已放置的皇后i，满足i - cols[i] == row - col。
副对角线冲突（右上-左下）：在同一条副对角线上的格子，其行号 + 列号的值是相等的。例如，(0,2), (1,1), (2,0) 在3x3棋盘上，其row + col都等于2。所以我们需要检查是否有已放置的皇后i，满足i + cols[i] == row + col。

使用一维数组后，检查一个位置是否合法的函数isValid(row, col, cols)，其时间复杂度是 O(row)，因为我们需要遍历前row行已放置的皇后进行检查。这比二维数组的 O(N) 扫描通常要快（因为row是当前行，通常小于N），并且省去了扫描整个行和列的过程。

2.3 极致的优化：位运算与布尔数组

当N继续增大（比如N>15），即使是O(N)的冲突检查也可能成为瓶颈。此时，我们可以利用位运算将冲突检查的时间复杂度降到 O(1)。

核心思想是：用三个整数（bitset）来分别记录列、主对角线、副对角线上是否已经被皇后占据。

columns：一个N位的比特位，columns[k]=1表示第k列已被占用。
main_diag：一个2N-1位的比特位。对于位置(i, j)，其主对角线索引为i - j + (N-1)（加上N-1是为了让索引非负）。main_diag[idx]=1表示该主对角线已被占用。
anti_diag：一个2N-1位的比特位。对于位置(i, j)，其副对角线索引为i + j。anti_diag[idx]=1表示该副对角线已被占用。

在放置第i行的皇后时，我们不再遍历前i行，而是直接计算：available_positions = ~(columns | main_diag >> (i) | anti_diag >> (N-1-i)) & ((1 << N) - 1)这个表达式（需要根据具体位移方向调整）能得到当前行所有可放置列的位置比特位。然后我们可以用lowbit操作（x & -x）来快速遍历所有可放置位置。这种方法将回溯变成了对状态比特位的操作，速度极快，是解决大规模N皇后（如N=15以上）竞赛级代码的首选。不过，其理解和实现门槛较高，我们会在基础解法之后探讨其变种。

对于SCAU OJ 18124这道题，通常N不会太大（一般不超过15），因此使用一维数组cols表示法在清晰度和效率之间取得了最好的平衡，也是教学中最常采用的方法。我们接下来的核心实现也将基于此法。

3. 核心算法：深度优先搜索与回溯框架

有了状态表示，我们就可以构建回溯算法的主体框架了。回溯算法通常通过递归来实现深度优先搜索（DFS），其模板非常清晰。

3.1 递归函数的设计

我们定义一个递归函数dfs(row, cols, n, solutions)。

row：当前正在尝试放置皇后的行号，从0开始。
cols：一维数组，记录已放置皇后的列位置。
n：棋盘大小N。
solutions：用于收集所有合法解的容器（例如，一个列表，里面每个元素是一个cols数组的副本）。

函数逻辑如下：

递归终止条件：如果row == n，说明我们已经成功地为前n行（即所有行）都放置了皇后，且没有发生冲突。此时，当前的cols数组记录了一个合法的解。我们需要将cols的当前状态保存到solutions中。这里有一个关键点：必须保存cols的副本，而不是引用，因为cols在回溯过程中会被修改。
遍历当前行的所有选择：对于当前行row，我们尝试将皇后放在每一列col(0 <= col < n)。
冲突检测：在放置前，调用isValid(row, col, cols)函数，检查位置(row, col)是否与第0行到第row-1行的皇后冲突。
做出选择（递归前进）：如果位置合法，我们执行cols[row] = col，做出选择。然后递归调用dfs(row+1, cols, n, solutions)，进入下一行。
撤销选择（回溯）：当递归调用返回后，意味着基于当前(row, col)选择的所有后续可能性都已经探索完毕（无论是找到了解还是所有尝试都失败）。此时，我们不需要显式地“撤销”cols[row]（因为下一次循环会直接覆盖它），但思想上要明白，我们回到了这个决策点，准备尝试下一个col。在某些更复杂的场景下，如果选择影响了其他全局状态，则需要显式恢复。

这个“选择-递归-返回”的过程，就像走迷宫：走到一个岔路口（第row行），选一条路（某个col）走下去，如果走到死胡同（后续无法放置），就退回到这个岔路口，尝试下一条路。

3.2 冲突检测函数`isValid`的实现细节

根据2.2节的描述，isValid函数的实现至关重要。一个清晰高效的实现如下：

def is_valid(row, col, cols): """ 检查在第row行第col列放置皇后是否合法。 cols: 列表，cols[i]表示第i行皇后所在的列。 """ for i in range(row): # 检查前row行 # 1. 检查列冲突 if cols[i] == col: return False # 2. 检查主对角线冲突：行差 == 列差 if i - cols[i] == row - col: return False # 3. 检查副对角线冲突：行和 == 列和 if i + cols[i] == row + col: return False return True

这里有一个常见的误解：是否需要检查行冲突？不需要。因为我们的dfs是一行一行放置的，cols数组每个行索引只会被赋值一次，天然保证了每行只有一个皇后。所以is_valid只需检查列和两条对角线。

3.3 收集解：输出格式的处理

SCAU OJ 18124题目的具体输出要求，需要查看题目描述。常见的N皇后问题输出有两种：

输出解的数量：只要求输出一共有多少种不同的摆放方法。
输出具体的解：要求以某种格式（如每行输出一个解的列位置序列）输出所有解。

我们的算法框架中的solutions列表就是用来存储所有解的。如果需要输出解的数量，直接返回len(solutions)即可。如果需要输出具体解，则遍历solutions，按照格式要求打印每个cols数组。

一个重要的注意事项：由于对称性，有些题目可能会要求去除通过旋转和镜像得到的重复解。但经典的N皇后问题通常将旋转和镜像视为不同的解，除非题目明确说明。SCAU 18124大概率是计算所有本质不同的解（即考虑对称性），但为了通用性，我们首先实现不考虑对称性的版本，这是基础。如果需要去重，那是一个更进阶的优化，涉及到群论中的对称性检测，我们可以在最后讨论。

4. 关键优化：剪枝的艺术

朴素的回溯会尝试所有N^N种可能的排列，然后通过is_valid过滤掉非法解。但很多非法情况其实可以提前发现，避免进入无用的递归分支，这就是“剪枝”。好的剪枝能极大提升算法效率。

4.1 最基本的剪枝：`is_valid`提前终止

这已经包含在我们的框架里了。在尝试每个col时立即检查合法性，如果不合法就跳过，不进行递归。这是回溯算法自带的剪枝。

4.2 利用对称性剪枝（针对只求解数量）

当N较大，且我们只关心解的数量时，可以利用棋盘的对称性大幅减少搜索量。棋盘有8种对称操作（旋转90°，180°，270°，以及水平、垂直、两条对角线的镜像）。这些操作会将一个解映射到另一个解。

核心思想：我们只搜索“标准型”的解，然后通过对称操作推导出其他解的数量。但如何定义“标准型”并高效搜索是一个复杂问题。一个相对简单实用的技巧是：固定第一行皇后的位置。

由于棋盘是旋转和镜像对称的，所有解必然可以通过对称操作，使得第一个皇后位于第一行中靠左的某些特定位置。例如，对于N×N棋盘，我们只需要让第一行的皇后放在第0列到第ceil(N/2) - 1列（即前半部分），然后搜索。最后将得到的解的数量乘以一个对称因子（通常是2或4，但需要小心边角情况，并且要考虑中心对称）。这种方法通常可以将搜索空间减少近一半或更多。

重要提示：这种剪枝会改变解的结构，使得我们收集的具体解列表不再是完整的、未去重的解。因此它仅适用于只求解数量的题目。如果题目要求输出所有解的具体排列，则不能使用此剪枝，或者使用后还需要通过对称操作还原出所有解，这会更复杂。

4.3 位运算优化（状态压缩）

如前所述，这是应对较大N的终极武器。我们不再使用cols数组和is_valid循环检查，而是用三个整数cols_mask,left_diag_mask,right_diag_mask来记录列、主对角线、副对角线的占用情况。

递归函数dfs_bit的步骤：

终止条件：如果row == n，找到一个解，计数器加一。
计算当前行可用的位置：
- occupied = cols_mask | left_diag_mask | right_diag_mask
- available = (~occupied) & ((1 << n) - 1)//(1<<n)-1生成低n位全是1的掩码，确保只取低n位。
当available不为0时循环：
- position = available & -available// 取出最低位的1，即一个可放置的位置。
- available &= available - 1// 将最低位的1置为0，表示尝试过这个位置。
- 递归调用dfs_bit(row+1, cols_mask | position, (left_diag_mask | position) << 1, (right_diag_mask | position) >> 1, n)。
  - cols_mask | position: 将当前列加入占用列掩码。
  - (left_diag_mask | position) << 1: 左对角线（主对角线）在下一行会整体左移一位。
  - (right_diag_mask | position) >> 1: 右对角线（副对角线）在下一行会整体右移一位。

这种方法的dfs函数内部没有循环，只有位操作，常数时间极低，因此速度非常快。对于N=15，普通回溯可能需要数秒甚至更久，而位运算优化可以在毫秒级完成。这是竞赛中必须掌握的技巧。

5. 代码实现与逐行解析

我们将基于一维数组的回溯法，实现一个能够输出所有解具体位置的Python程序，并详细注释。

def solve_n_queens(n): """ 解决N皇后问题，返回所有解的列表。 每个解是一个列表，表示每一行皇后所在的列（0-indexed）。 """ def is_valid(row, col, cols): """检查当前位置(row, col)是否与已放置的皇后冲突。""" for i in range(row): # 检查同一列 if cols[i] == col: return False # 检查主对角线：行差等于列差 if i - cols[i] == row - col: return False # 检查副对角线：行和等于列和 if i + cols[i] == row + col: return False return True def dfs(row, cols, solutions): """ 深度优先搜索回溯。 row: 当前要放置皇后的行。 cols: 当前已放置皇后的列位置列表。 solutions: 存储所有解的列表。 """ # 终止条件：所有行都已成功放置皇后 if row == n: # 注意：这里必须添加cols的副本，因为cols在回溯中会被修改 solutions.append(cols[:]) return # 尝试在当前行的每一列放置皇后 for col in range(n): if is_valid(row, col, cols): # 做出选择 cols[row] = col # 递归进入下一行 dfs(row + 1, cols, solutions) # 回溯：在cols中，当前位置会被下一次循环覆盖，无需显式重置。 # 但如果cols[row]有其他用途，或需要恢复状态，可以在这里做。 # cols[row] = -1 # 显式重置，清晰但非必须 # 初始化：cols列表，初始值可以任意，通常用-1或0，我们会在dfs中赋值 cols = [-1] * n solutions = [] # 从第0行开始搜索 dfs(0, cols, solutions) return solutions # 示例：解决8皇后问题，并打印前3个解 if __name__ == "__main__": n = 8 all_solutions = solve_n_queens(n) print(f"Total solutions for {n}-Queens: {len(all_solutions)}") for idx, sol in enumerate(all_solutions[:3]): print(f"Solution {idx + 1}: {sol}") # 可视化打印（可选） board = [['.' for _ in range(n)] for _ in range(n)] for r, c in enumerate(sol): board[r][c] = 'Q' for row in board: print(' '.join(row)) print()

关键代码解析：

cols = [-1] * n：初始化一个长度为n的列表，用-1填充，表示所有行的皇后位置尚未确定。-1是一个常用的哨兵值。
solutions.append(cols[:])：这是极易出错的地方。如果我们直接append(cols)，那么加入solutions的是cols列表的引用。在后续的回溯中，cols列表的内容会被修改，导致solutions中所有之前存储的解都变成最终cols的状态（通常是无效的）。使用cols[:]或list(cols)创建了一个当前状态的副本，从而正确保存了每一个解。
递归调用dfs(row+1, cols, solutions)后，我们没有写cols[row] = -1。这是因为在下一轮for col in range(n)循环中，cols[row]会被新的col值直接覆盖。所以这个重置操作是隐式的。写上cols[row] = -1会让“撤销选择”这一步更清晰，但并非必需。我个人倾向于写上，因为这样更符合回溯“恢复现场”的语义，尤其是在状态更复杂时。
is_valid函数中的循环for i in range(row)：只检查了前row行，这正是我们需要的。我们不需要检查当前行之后的行，因为它们还没有放置皇后。

6. 性能分析与实测考量

理解了算法，我们还需要知道它的表现如何，以及在实际做题（如SCAU OJ）时需要注意什么。

6.1 时间复杂度：它到底有多“慢”？

回溯算法的时间复杂度很难用精确的表达式表示，因为它依赖于剪枝的效果。最坏情况下，我们需要探索每一行的每一列，复杂度是 O(N^N)，这是一个天文数字。但得益于皇后问题的强约束（每行、每列、每对角线唯一），实际搜索的节点数远小于 N^N。

对于较小的N，我们可以直接计算解的数量：

N=1: 1
N=2: 0
N=3: 0
N=4: 2
N=5: 10
N=6: 4
N=7: 40
N=8: 92 (这就是著名的八皇后问题，有92个解)
N=9: 352
N=10: 724
N=11: 2680
N=12: 14200
N=13: 73712
N=14: 365596
N=15: 2279184

可以看到，解的数量增长非常快。我们的算法需要遍历所有可能的解，因此运行时间也随N指数级增长。使用普通的一维数组回溯法，在普通PC上，N=13可能就需要几秒，N=15可能需要几十秒甚至几分钟。

6.2 空间复杂度

主要空间消耗来自：

递归调用栈：深度为N，所以是 O(N)。
cols数组：O(N)。
solutions列表：如果需要存储所有解，这是主要的空间消耗。每个解是一个长度为N的列表，共有S(N)个解，所以空间复杂度是 O(N * S(N))。对于N=15，这将是数千万个整数，内存消耗巨大（约227万 * 15 * 4字节 ≈ 130MB，仅存储列索引）。如果题目只要求解的数量，我们可以只维护一个计数器，将空间复杂度降为 O(N)。

OJ做题实战建议：

仔细阅读输入输出要求：SCAU 18124是单次输入一个N，还是多组测试数据？是输出解的数量还是具体解？输出格式是否有特殊要求（如每个解用空格隔开，每行一个解）？
根据N的范围选择算法：如果题目给出的N最大为10或12，那么基础回溯法完全够用。如果N可能到15或更大，并且时间限制严格，就必须考虑位运算优化，甚至打表（预处理出所有N的解的数量，直接查表输出）。
使用高效的编程语言：在OJ上，Python可能对于N>13的题目就有些吃力了，而C++使用位运算优化则可以轻松处理N=15。了解你所用语言在OJ环境下的性能特点。
本地测试：在提交前，用边界值（如N=1, N=最大允许值）测试你的程序，确保不会超时或内存溢出。

6.3 位运算优化版本代码示例

为了完整性，这里给出一个只统计解数量的位运算优化Python版本。注意，Python的整数可以当作任意长度的位图来用，非常方便。

def total_n_queens(n): """使用位运算计算N皇后问题的解的数量。""" def dfs(row, col_mask, left_diag_mask, right_diag_mask): count = 0 # 生成所有可放置的位置：取反后，1表示可放置 # (1 << n) - 1 生成一个低n位全是1的掩码，确保只考虑n列 available_positions = (~(col_mask | left_diag_mask | right_diag_mask)) & ((1 << n) - 1) while available_positions: # 取出最低位的1（一个可放置的列） position = available_positions & -available_positions # 将这个位置从可用位置中移除 available_positions &= available_positions - 1 # 递归进入下一行 # 新的列掩码：当前列掩码 或 当前位置 new_col_mask = col_mask | position # 新的左对角线掩码：当前掩码 或 当前位置，然后左移一位（因为对角线在下一行的影响） new_left_diag_mask = (left_diag_mask | position) << 1 # 新的右对角线掩码：当前掩码 或 当前位置，然后右移一位 new_right_diag_mask = (right_diag_mask | position) >> 1 # 如果已经放满了n个皇后 if row == n - 1: count += 1 else: count += dfs(row + 1, new_col_mask, new_left_diag_mask, new_right_diag_mask) return count # 从第0行开始，所有掩码初始为0（表示没有位置被占用） return dfs(0, 0, 0, 0) # 测试 if __name__ == "__main__": for n in range(1, 13): print(f"N={n}: {total_n_queens(n)}")

这个版本没有使用cols数组，也没有is_valid函数，所有冲突检测通过位运算在常数时间内完成，效率极高。

7. 常见陷阱与调试技巧

即使理解了算法，实现时也可能掉进一些坑里。下面是我在多次实现N皇后问题中总结的一些经验。

7.1 深拷贝与浅拷贝之坑

如前所述，在保存解solutions.append(cols)时，必须使用副本cols[:]。这是Python初学者（甚至是有经验者一时疏忽）最容易犯的错误。症状是：最终solutions列表里所有的解都是一样的，而且是最后一次递归结束时的cols状态。调试方法：在递归终止条件处打印cols和id(cols)，你会发现每次添加的都是同一个列表对象。改为cols[:]即可。

7.2 索引与边界错误

行列索引从0开始还是1开始？算法中通常使用0-index（0到N-1）更自然，因为数组索引也是从0开始。但有些题目输出要求可能是1-index。务必在输出前进行转换（col+1）。
对角线索引计算：主对角线row - col可能是负数，这在用数组记录对角线状态时需要注意偏移（row - col + N - 1）。在我们的循环检查法中，直接比较等式即可，没有问题。但在位运算或使用布尔数组记录对角线状态时，必须处理负数索引。

7.3 递归深度限制

Python默认的递归深度限制（sys.getrecursionlimit()）通常是1000。对于N皇后问题，N最大一般也就几十，递归深度为N，所以不会触发这个限制。但如果你的递归实现有问题（比如终止条件写错），可能导致无限递归，最终触发RecursionError。

7.4 性能瓶颈定位

如果你的程序对于某个N运行特别慢，可以尝试以下方法定位：

添加计数器：在dfs函数入口增加一个全局计数器，统计递归调用的次数。这能直观反映算法探索的节点数。对比不同剪枝策略带来的节点数减少。
使用性能分析工具：Python的cProfile模块可以告诉你程序时间花在了哪里。你可能会发现is_valid函数是热点，这就提示你可以考虑位运算优化。
输出中间状态：对于小的N（如4或5），可以打印出每次尝试放置和回溯的过程，帮助你理解算法的执行流程，确认剪枝是否生效。

7.5 对称性处理的复杂性

如果你尝试实现利用对称性剪枝来只计算一半搜索空间，要特别注意N为奇数或偶数时的不同处理，以及皇后放在第一行正中间列时的特殊对称性（它自身的镜像可能就是它自己）。一个稳妥的方法是：先搜索所有第一行皇后在前半部分列的解，对于每个找到的解，检查它是否是通过某个对称操作从另一个“更小”的解得到的，如果是则不计入。这实现起来比较繁琐，除非题目N很大且必须优化，否则不建议在初版实现中引入。

8. 从N皇后到更广阔的回溯世界

通过彻底拆解N皇后问题，我们实际上掌握了一套解决约束满足问题（CSP）的回溯模板。很多问题都可以套用这个“选择-验证-递归-回溯”的框架。

数独求解：每个格子是一个决策变量（数字1-9），约束是行、列、九宫格内不重复。我们可以用类似的DFS+回溯，并加上更复杂的启发式（如选择可能值最少的格子优先填充）。
全排列/组合问题：给定数组，生成所有不重复的排列或组合。状态可以是当前已构建的序列，选择是剩余可用的元素。
图着色问题：用M种颜色给地图着色，相邻区域颜色不同。决策变量是每个区域的颜色。
子集和问题：从集合中找出和为特定值的子集。

N皇后问题之所以是经典，就在于它用最简洁的形式，包含了回溯算法的所有核心要素：状态表示、选择列表、约束条件、递归推进、回溯恢复、剪枝优化。把它吃透，再遇到其他回溯问题，你就能迅速抓住本质，设计出正确的算法结构。

最后，在SCAU OJ 18124或者其他平台提交时，记得根据题目要求调整输入输出。可能只需要将solve_n_queens(n)返回的列表长度输出，或者按照特定格式输出每个解的列编号。多思考，多动手，从理解到AC，这个过程本身就是算法学习最大的乐趣。

查看全文

http://www.jsqmd.com/news/1314706/