BM59　N皇后问题¶

较难通过率 43.54%python3核心代码模式样例通过牛客 AC递归

牛客原题　源码

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

一句话

逐行放皇后，用列与两条对角线的占用集合剪枝，回溯累加解的个数。

解题思路¶

这题考什么¶

要求「任意两个皇后不同行」，那就干脆一行放一个：枚举对象从 n*n 个格子降到「第 r 行放第几列」，搜索树的深度固定是 n，同行冲突被枚举方式本身消化掉，不必再检查。

剩下三个约束都能 O(1) 判断，关键是给每条线找一个不变量：

同列        c 相同
主对角线    从左上到右下，r - c 相同
副对角线    从右上到左下，r + c 相同

于是维护三个集合 cols / diag / anti，放子时把 c、r-c、r+c 记进去，撤销时删掉。第 r 行试列 c 前先查这三个集合，命中任何一个就跳过。

r=0  . Q . .      cols={1} diag={0-1=-1} anti={0+1=1}
r=1  . . . Q      c=3 与已放的都不冲突 -> 继续下一行
r=2  Q . . .
r=3  . . Q .      放满 4 行 -> 解数 +1

回溯与剪枝的一般写法见记忆化搜索与剪枝。

数据规模与复杂度¶

1 <= n <= 9，时限「其他语言 2 秒」。深度 n、每层至多 n 个分支，上界 O(n!)；三个集合的剪枝把实际展开的节点压到万级以内，n=8 有 92 种摆法、n=9 有 352 种，最大的一档也是眨眼跑完。空间 O(n)：递归深度 n，三个集合各最多 n 个元素。不剪枝的写法（放满 n 个再回头两两验证）要枚举 n^n = 3.9e8 种放法，量级完全不同。

坑在哪¶

返回的是解的个数（一个整数），不是棋盘。递归里只需累加计数，不必拼出每种摆法的字符串，省掉的正是这类题最耗时的一段。
两条对角线的不变量不能弄混：主对角线是 r - c、副对角线是 r + c。两条都用 r + c 会漏判一半冲突，答案偏大。
r - c 可能是负数。这里用集合存标识，负下标无所谓；若改用数组标记，必须整体加偏移量 n-1，否则负下标会绕到数组尾部误判。
撤销要三个集合一起删，漏掉任何一个都会让后续兄弟分支误以为某条线仍被占用，解数偏小且没有任何报错。
n=1 的答案是 1（示例 1），不是 0——一个皇后自己不与任何皇后冲突。

样例复核¶

n=4 时，第 0 行放列 1、第 1 行只能放列 3、第 2 行只能放列 0、第 3 行只能放列 2，得到一种摆法；镜像的那一种由第 0 行放列 2 展开而来，共 2 种，与题面描述一致。

参考实现¶

solutions/nowcoder/BM59/sol.py
from typing import List, Optional


class Solution:
    def Nqueen(self, n: int) -> int:
        # 一行放一个皇后，同行冲突自动排除；剩下三种冲突各用一个集合 O(1) 查
        cols: set = set()      # 已占用的列
        diag: set = set()      # 已占用的主对角线，标识 r - c
        anti: set = set()      # 已占用的副对角线，标识 r + c

        def place(r: int) -> int:
            if r == n:         # n 行都放下了，凑出一种摆法
                return 1
            # 只累加解的个数，不拼棋盘——题目要的就是一个整数
            total = 0
            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)
                total += place(r + 1)
                # 撤销必须三个集合一起删，漏一个就会污染后面的兄弟分支
                cols.remove(c)
                diag.remove(r - c)
                anti.remove(r + c)
            return total

        return place(0)

BM59 N皇后问题¶