你好，同学。欢迎来到 NOI 专题训练。

今天我们要研究的是 N 皇后 II (N-Queens II)。与 I 题不同，这一题不需要我们输出具体的棋盘布局，只需要求出符合条件的解的总数。在 NOI 竞赛中，这类题目通常是用来考察搜索效率优化和位运算加速的经典案例。

一、 题目描述 (NOI 风格)

题目名称：N 皇后 II (N-Queens II) 时间限制：1.0s 内存限制：256MB

【问题描述】 $n$ 皇后问题研究的是如何将 $n$ 个皇后放置在 $n \times n$ 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 $n$，请你返回所有不同的 $n$ 皇后问题解决方案的个数。 注意：皇后可以攻击同一行、同一列或同一条斜线上的任何棋子。

【输入格式】 输入仅一行，包含一个整数 $n$。

【输出格式】 输出一个整数，表示不同解决方案的总数。

【样例输入 1】

4

【样例输出 1】

2

【样例输入 2】

1

【样例输出 2】

1

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 9$。 (注：在 NOI 实际考场中，$n$ 往往会达到 13~15，此时必须使用位运算优化才能满分。)

二、 预备知识点

1. 回溯算法 (Backtracking)：通过深度优先遍历搜索空间，并在不符合条件时撤销操作。
2. 状态压缩 (State Compression)：利用整数的二进制位来表示棋盘上某一行的占用情况。
3. 位运算 (Bit Manipulation)：
   • x & -x：取出最低位的 1 (Lowbit)。
   • x & (x - 1)：去掉最低位的 1。
   • 位移运算 << 和 >>：处理对角线在下一行的投影。

三、 启发式思路引导

请在草稿纸上跟随我的逻辑进行推理：

1. 核心约束转化

皇后互相攻击的三个维度：

• 列约束：如果第 $r$ 行第 $c$ 列放了皇后，那么后面所有行的第 $c$ 列都不能放。
• 左斜线 (r-c)：随着行数增加，影响位置向左偏移。
• 右斜线 (r+c)：随着行数增加，影响位置向右偏移。

2. 位运算的神奇之处

假设 $n=4$，我们用三个整数 col, ld, rd 记录当前被占用的位：

• col = 0010 (第 2 列被占)
• ld (Left Diagonal) 和 rd (Right Diagonal)：在递归进入下一层时，ld 应该左移一位，rd 应该右移一位。
• 可用位置：~(col | ld | rd) & ((1 << n) - 1)。

四、 复杂度分析思考过程

• 时间复杂度：$O(N!)$。
  • 虽然是指数级，但由于皇后之间的约束极强，剪枝效率极高。
  • 对于 $n=13$，方案数约 7.3 万，位运算可以在 0.01s 内跑完。
• 空间复杂度：$O(N)$。
  • 主要是递归的深度，位运算版甚至不需要显式开辟标记数组。

五、 算法流程图 (位运算最优解)

graph TD
    Start(开始) --> Init(初始化 ans 等于 0)
    Init --> SetMask("计算全满状态 mask = (1 左移 n 位) 减 1")
    SetMask --> CallDFS("调用 DFS(row=0, col=0, ld=0, rd=0)")

    subgraph DFS_Process [递归搜索函数]
    BaseCheck{col == mask ?}
    BaseCheck -- 是 --> AddAns(ans 增加 1)
    BaseCheck -- 否 --> GetPos("计算可用位置 pos = mask 且非(col 或 ld 或 rd)")
    
    GetPos --> LoopStart{pos 不等于 0 ?}
    LoopStart -- 是 --> PickOne("取出最低位的 1: p = pos 且 -pos")
    PickOne --> Recurse("递归进入下一行")
    Recurse --> StateUpdate("DFS(row+1, col 或 p, (ld 或 p)左移1位, (rd 或 p)右移1位)")
    StateUpdate --> ClearPos("移除该位: pos = pos 且 (pos-1)")
    ClearPos --> LoopStart
    
    LoopStart -- 否 --> Return((返回上一层))
    end

    AddAns --> Return
    Return --> End(输出 ans)

六、 读题关键词总结

1. “返回解的个数”：这提醒我们不需要维护复杂的棋盘二维数组，只需要维护状态标记即可，极大地有利于空间优化和位运算的应用。
2. “斜线攻击”：这是题目最难处理的约束。看到“斜线”，脑海中应立即反应出 (r+c) 和 (r-c) 的不变性，或者在位运算中反应出 << 1 和 >> 1 的状态转移。
3. “$n \le 9$”：这是 LeetCode 的数据量。但在 NOI 辅导中，请记住：只要 $n \le 16$，位运算回溯都是此类问题的终极标准答案。

教练寄语： 同学，N 皇后 II 不仅仅是搜索，它更是你理解“计算机底层运算如何加速逻辑判断”的敲门砖。当你能熟练写出位运算版本时，你对“状态”的理解已经跨越了初级选手的门槛。加油！