LeetCode 51. N 皇后：回溯与剪枝的巅峰示范

N 皇后（LeetCode 51，Hard）是回溯与剪枝的巅峰示范：n×n 的棋盘上放 n 个皇后，任意两个不能同行、同列、同对角线，求所有放置方案。它的价值不在答案（解的数量没有闭式公式，n=8 有 92 个解纯属历史趣味），而在它完整示范了回溯搜索的两个核心工程：约束检查怎么做才快（暴力检查 O(n) → 集合 O(1) → 位运算 O(1)）与剪枝怎么把指数的搜索树剪成可行规模（每行只有一个皇后的天然约束 + 逐行放置的顺序化）。

基础版：逐行放置与集合检查

关键的观察：n 个皇后放在 n 行——每行恰好一个皇后（若某行有两个，它们同列冲突；若某行没有，必有另一行两个——抽屉原理）。于是搜索被顺序化：按行放置，第 i 行的决策只是「选哪一列」——决策树从 n^(n²) 的天文数字坍缩为 n! 量级。约束检查：同列冲突用 cols 集合；两条对角线——左下到右上的对角线上，row - col 为定值；左上到右下的对角线上，row + col 为定值——用 row-col 与 row+col 两个集合编码对角线，是本题最优雅的技巧（把二维的斜线约束压成两个一维集合）：

def solve_n_queens(n: int) -> list[list[str]]:
    cols, diag1, diag2 = set(), set(), set()
    queens = []                     # queens[i] = 第 i 行皇后所在列
    result = []

    def backtrack(row: int):
        if row == n:                # n 行都放下了：一个完整解
            result.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue            # 剪枝：三组约束任一冲突即跳过
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            queens.append(col)
            backtrack(row + 1)
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
            queens.pop()

    backtrack(0)
    return result

三个集合的增删与递归严格对称（本库《全排列》的撤销纪律），时间复杂度上界 O(n!)——但剪枝让实际的搜索空间远小于上界：大量分支在第一两行就被「列冲突」砍断，n=8 的全部求解在毫秒级完成。

进阶版：位运算——把三组约束压进三个整数

性能与优雅的进一步升级是位运算版：每一行可放的位置用 n 位整数表示（1 = 可放），三组约束各用一个整数记录——cols 的第 c 位为 1 表示第 c 列已占用；对角线的位表示需要在「下一行」时移位：row - col 对角线下一行偏移一位（左移或右移，取决于方向编码），于是下一行的「可用位置」= ~(cols | (diag1 << 1) | (diag2 >> 1)) 的低位——三组约束的三次移位一次或运算，候选位置直接由位运算给出；再配合「取最低位的 1」（pos & -pos，O(1) 枚举候选）与「清零」（pos & pos-1），递归的每一层只有几个位运算。位运算版是 N 皇后性能优化的经典示范（八皇后的全部解在微秒级），它的可读性代价也真实存在——生产代码中集合版足够，位运算版属于「性能极致 + 想展示位运算功力」的场景。

剪枝的通用启示与「计数变体」

N 皇后示范的剪枝原则可以带走三条。原则一：约束要编码成 O(1) 检查——「同列」「同对角线」的集合/位运算编码，让每次剪枝的代价是常数；暴力地「检查新皇后与已有所有皇后」是 O(n) 且容易写错。原则二：顺序化搜索消灭重复计数——「每行一个」的观察把组合搜索变成排列搜索，这是「利用问题结构缩小搜索树」的典范（类似的还有：数独按格子顺序填、图着色按节点顺序染）。原则三：对称性剪枝（可选进阶）——棋盘左右对称，第一行皇后只需试左半边（其余镜像），可再省一半。计数变体（LeetCode 52：只求数量不求棋盘）：把「收集棋盘」换成「计数器加一」即可，其余不变——同一套搜索，产出两种答案；这也是回溯的通用性质：搜索树不变，叶子上的「记录方式」决定你输出的是方案还是数量。

对称性剪枝与「解的表示」：位运算版进阶细节

位运算版的 N 皇后还有两个进阶细节值得单独记录。细节一：对称性剪枝的实现——第一行皇后只需尝试左半边（n 为奇数时中间列单独算一次），其余解是镜像：实现上 for col in range(n // 2) 加上（奇数时）中列的特判——镜像剪枝省一半搜索，但只对「求全部解」有效，「求方案数」的镜像解数量 = 2×（半边的解数）需在计数时处理。细节二：解的表示——本库正文的 queens 列表记录「每行的列」，输出棋盘时用字符串构造；位运算版的输出需要额外从「列位掩码」反解出列号（bit_position = (mask & -mask).bit_length() - 1）——位运算版的效率优势与表示劣势并存，转换层的代码是位运算方案被诟病的可读性代价。最后一个数学趣闻：n 皇后的解数量没有闭式公式（n=8 是 92、n=9 是 352、增长无规律可循），它是「枚举类问题」的典型——有些计数问题天然没有数学捷径，搜索是唯一诚实的答案——这也是回溯作为「最后一道防线」算法的存在的意义。

N 皇后的「启发式变体」：最小冲突算法

N 皇后还有一个非回溯的解法家族值得认识：最小冲突算法（Min-Conflicts，局部搜索）——随机放置 + 反复选择「冲突最少的列」移动冲突的皇后，对大规模 n（上千皇后）在极短时间内找到解（回溯在 n=30+ 就开始吃力，局部搜索轻松处理千皇后）。它展示的另一个维度：「找一个解」与「枚举所有解」是两种完全不同的问题——回溯擅长后者（系统性、不重不漏），局部搜索擅长前者（快速、随机化）。产业映射：调度问题、资源分配——现实世界的「N 皇后放大版」几乎都是「找一个可行解/找较优解」而非「枚举全部」——这就是为什么工业求解器（运筹优化、SAT 求解器）用的都是局部搜索/约束传播/线性规划的混合，而不是朴素回溯。对本篇的定位修正：回溯是「理解约束搜索的教学最优解 + 小规模的最优工程解」，规模上去之后的世界属于启发式与数学规划——知道每个工具的能力半径，比掌握工具本身更接近专家。

与 N 皇后同族的棋盘约束题：数独求解器的骨架对比

N 皇后的回溯骨架，与它的同族明星——数独求解器（LeetCode 37）——对比着看更清楚。数独的约束：行、列、3×3 宫各不重复 1-9——约束的编码与 N 皇后同款（行/列/宫三个集合组，宫的编码是 (row//3)*3 + col//3——把 3×3 宫映射成一维编号）；搜索的顺序优化：数独的「最少候选优先」（MRV 启发式——每次选择候选数字最少的空格填）是它的效率关键（N 皇后按行顺序即可，数独不挑顺序就会慢得离谱——填哪个格子的顺序，是数独回溯的成败手）；回溯的差异：数独的「填错回退」要撤销多个格子的状态吗——不用，回溯天然只撤销当前分支的选择（递归栈保证了这一点）。对比的结论：约束搜索题的骨架（选择→检查→递归→撤销）完全一致，差异全在「约束的编码效率」与「搜索顺序的启发式」两处——棋盘类回溯的功夫，七分在约束编码，三分在搜索顺序。

n 皇后的数学前沿：解数量的已知边界

n 皇后还有一个数学视角的边角值得知道：解数量没有公式，但有已知序列与计算纪录。已知的解数量序列（OEIS A000170）：n=1 到 n=27 的解数量已被算出（n=27 的数量是 2.34×10^17 级——2022 年用大规模并行计算历时数月完成，是组合计算的重要里程碑）；n=28 起仍未算出——这个问题的计算难度本身就是研究价值（没有闭式公式、没有多项式时间的计数算法——#P 完全问题的邻居）。回溯在其中的位置：朴素回溯在 n=15 左右就吃力，实用的计数靠对称性剪枝（镜像减半）+ 位运算 + 大规模并行 + 高级剪枝（冲突前瞻）的组合把边界推到 n=27——每一代研究者把边界推一格，靠的不是算法革命，是工程与剪枝的积累。给学习者的视野结论：N 皇后是「简单规则、无公式解、指数搜索」三个属性的组合体——它是理解「约束满足问题（CSP）」复杂度本质的最佳教具——从这个教具出发，往上看是 SAT 求解器与 CSP 的工业世界，往下看是回溯的教学世界——本篇的集合版代码，是两个世界之间的第一级台阶。

N 皇后的位运算优化详解：三组约束的编码

位运算版的核心是把三组约束编码为三个整数的位操作。cols 的第 c 位为 1 表示第 c 列已占用——检查第 c 列是否可用就是检查 cols 的第 c 位是否为 0。diag1 和 diag2 的位编码更巧妙：每下移一行，对角线的「影响位置」在位图上偏移一位——diag1 左移 1 表示「左下对角线在下一行的影响位置右移一位」（方向取决于编码约定），diag2 右移 1 同理。下一行的可用位置就是三个约束位图的「取反再取与」——available = ~(cols | diag1_shifted | diag2_shifted) 的低位。枚举可用位置用「取最低位的 1」（pos & -pos）并清零（pos &= pos-1）——O(1) 的枚举。位运算版的可读性代价真实存在——生产代码中集合版足够，位运算版属于性能极致场景。

小结

这篇收成四条：「每行恰好一个皇后」的抽屉原理把搜索顺序化，决策树从 n^(n²) 坍缩为 n! 量级——利用问题结构缩小搜索树是剪枝的第一次胜利；对角线用 row−col 与 row+col 两个集合编码，把二维斜线约束压成 O(1) 检查——这是本题最优雅的技巧；位运算版把三组约束压进三个整数，移位表达对角线在下一行的偏移——性能极致但有可读性代价；剪枝的三条通用原则——约束 O(1) 编码、顺序化搜索、对称性剪枝，适用于一切「棋盘式」回溯问题。N 皇后之后，回溯系列（全排列 → 括号生成 → N 皇后）的骨架与剪枝全部到齐——剩下的，是拿这套骨架去解任何新的约束搜索题。

参考资料

• LeetCode 51/52. N-Queens I & II —— 题目与官方题解
• 本库前篇：《LeetCode 46. 全排列》《LeetCode 22. 括号生成》—— 回溯骨架的前两课
• 位运算技巧（pos & -pos 取最低位）的经典出处——二进制枚举子集的标准手法