LC51　N 皇后¶

困难通过率 75.2%python3核心代码模式回溯样例通过牛客 AC数组回溯X 算法

牛客原题　源码

讲解章节：DFS 深度优先搜索

一句话

逐行放一个皇后，用三个集合记住已被占的列与两条对角线，冲突就换列。

解题思路¶

这题考什么¶

先做一步降维：n 个皇后放进 n 行且互不同行（同行必然互相攻击），所以每行恰好一个皇后，问题变成「为第 0 到 n-1 行各挑一个列号」。行冲突由这个结构天然免除，剩下三种冲突要判：

同列两个皇后的列号相等主对角线行减列相等（左上到右下方向，这个差在一条对角线上是常量）副对角线行加列相等（右上到左下方向，这个和在一条对角线上是常量）

n = 4 的一个解         行-列 与 行+列
. Q . .   (0,1)        -1 / 1
. . . Q   (1,3)        -2 / 4
Q . . .   (2,0)         2 / 2
. . Q .   (3,2)         1 / 5
四个列号、四个差、四个和各不相同 -> 互不攻击

于是判冲突从「回头扫已放的每个皇后」的 O(行数) 降成三次集合查询 O(1)。逐行深搜 + 冲突剪枝 + 撤销标记，就是回溯的「选择 -> 递归 -> 撤销」三步。通用写法见 DFS 深度优先搜索。

数据规模与复杂度¶

1 <= n <= 9。n 皇后解的个数增长很慢：n = 8 有 92 个解，n = 9 有 352 个。不剪枝时搜索树是 n 的 n 次方 = 9 的 9 次方约 3.9e8 个叶子，必然超时；加上三条冲突剪枝后，第 r 行的可选列被前 r 行压得只剩少数几个，本地实测递归被调用的次数 n = 8 时 2057 次、n = 9 时 8394 次，比不剪枝的上界小了五个数量级，毫秒级跑完。每找到一个解要拼 n 个长度 n 的字符串，O(n 的平方) = 81 次字符操作。空间 O(n)：三个集合与列号栈都只存 n 个元素，递归深度 n。

坑在哪¶

返回的是棋盘列表，不是解的个数。每个解是 n 个长度为 n 的字符串，皇后所在列写 'Q'、其余写 '.'。牛客 BM59 的同题恰好相反，只要个数；照搬那份代码返回整数，这里会直接判错。
对角线的判据别记混：主对角线（左上到右下）上行减列是常量，副对角线（右上到左下）上行加列是常量。两者写反虽然仍是两族平行线，但配对错误会漏解或放出互相攻击的摆法。
行减列可能是负数（第 0 行第 3 列是 -3）。用集合存所以无所谓；若改用定长数组当标记，必须把下标偏移 n-1，否则负下标会绕回数组尾部，把两条毫不相干的对角线当成同一条。
三个集合的标记必须在递归返回后全部还原，与放置时一一对应。少还原任何一个，这一行换下一列时会读到脏标记，合法摆法被误判成冲突，解数直接偏少（n = 4 时可能一个解都找不到）。
只在最后一行放完（r == n）时才拼棋盘字符串。中途拼是白拼—— 绝大多数分支会在半路被剪掉，提前构造字符串是纯浪费。
n = 1 时答案是 [["Q"]]，不是空列表：一个皇后单独放在 1x1 棋盘上不与谁冲突。逐行递归天然覆盖这一档，无须特判。
本题在 meta.json 的 judge 里配了 unordered：官方题解也没规定解与解之间的先后，两个不同摆法谁先输出都对。放宽的只是顶层顺序—— 每个解内部的 n 个字符串是按行号从上到下排列的，行序错了棋盘就不是那个棋盘，这一层绝不放宽。顺序放宽也不等于内容放宽：同一个摆法吐两遍照样判错，本题「每行恰好一个皇后 + 逐行推进」保证了每个摆法只会被枚举到一次。

样例复核¶

n = 4：第 0 行放第 1 列后，第 1 行的 0、1、2 列分别撞上副对角线、同列、主对角线，只能放第 3 列，继而第 2 行只能放第 0 列、第 3 行只能放第 2 列，得到第一个解 [".Q..","...Q","Q...","..Q."]；第 0 行改放第 2 列同理得到第二个解。第 0 行放第 0 列或第 3 列时后续会全部走死，共 2 个解，与样例一致。

参考实现¶

solutions/leetcode/LC51/sol.py
from typing import List, Optional


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        # 三族冲突各存一份：列号、主对角线（行减列）、副对角线（行加列）
        # 同一条对角线上这两个值分别是常量，所以判冲突是 O(1) 的集合查询
        cols = set()
        diag = set()
        anti = set()
        # queens[r] 记第 r 行皇后所在的列，最后一行放完才据此拼棋盘
        queens = []

        def dfs(r: int) -> None:
            # 每行恰好一个皇后，r 到达 n 说明 n 个皇后都放好了，此刻才拼字符串
            if r == n:
                # 第 c 列写 'Q'，左右各补相应个数的 '.'，凑成长度 n 的一行
                res.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
                return
            # 本行逐列试放；行冲突由「一行一个皇后」的结构天然免除，不必判
            for c in range(n):
                # 三条剪枝：同列、同主对角线（行减列相同）、同副对角线（行加列相同）
                if c in cols or (r - c) in diag or (r + c) in anti:
                    continue
                # 选：三处标记同时置位，下一行才能看到本行的占用
                cols.add(c)
                diag.add(r - c)
                anti.add(r + c)
                queens.append(c)
                dfs(r + 1)          # 递归：去摆下一行
                # 撤销：四处状态全部还原，少还原一处，本行换列时就会读到脏标记
                queens.pop()
                cols.remove(c)
                diag.remove(r - c)
                anti.remove(r + c)

        dfs(0)
        return res

LC51 N 皇后¶