你好，同学！今天我们来挑战搜索算法中极其经典、甚至被视为“搜索入门仪式”的题目——N 皇后问题。

在 NOI 竞赛中，N 皇后不仅是回溯算法的教科书级案例，更是我们学习几何关系转数组索引以及位运算加速搜索的最佳练兵场。

一、 题目描述 (NOI 风格)

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

【问题描述】 按照国际象棋的规则，皇后可以攻击与她在同一行、同一列或同一条斜线上的棋子。 $n$ 皇后问题研究的是如何将 $n$ 个皇后放置在 $n \times n$ 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 $n$，请你返回所有不同的 $n$ 皇后问题的解决方案。 每一种解法包含一个不同的 $n$ 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

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

【输出格式】 输出若干个解。每个解由 $n$ 行字符串组成，方案之间用一个空行隔开（NOI 形式通常要求输出所有方案，具体格式参考样例）。

【样例输入】

4

【样例输出】

. Q . .
. . . Q
Q . . .
. . Q .

. . Q .
Q . . .
. . . Q
. Q . .

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 9$。

二、 预备知识点

1. 回溯算法 (Backtracking)：核心在于“尝试”与“恢复现场”。
2. 二维坐标的几何性质：
   • 列约束：$col$ 相同。
   • 主对角线约束（左上到右下）：行与列的差 $row - col$ 为定值。为防止索引为负，通常使用 $row - col + n$。
   • 副对角线约束（右上到左下）：行与列的和 $row + col$ 为定值。
3. STL 容器：使用 vector<string> 存储中间状态。

三、 启发式思路引导：草稿纸上的推理

皇后的攻击范围是“米”字型。由于每一行只能放一个皇后，我们可以逐行放置。

1. 约束条件的数组化

请在草稿纸上画一个 $4 \times 4$ 的格子，观察对角线：

• 坐标 (1,1)：它的主对角线经过 (0,0), (2,2)；副对角线经过 (0,2), (2,0)。
• 规律：
  • 同一条主对角线上，所有点的 row - col 都相等（例如：1-1=0, 0-0=0, 2-2=0）。
  • 同一条副对角线上，所有点的 row + col 都相等（例如：1+1=2, 0+2=2, 2+0=2）。

2. 状态维护

我们需要三个布尔数组来瞬时判断某个位置是否能放皇后：

• bool cols[n]：记录哪一列被占了。
• bool diag1[2*n]：记录哪条主对角线被占了。
• bool diag2[2*n]：记录哪条副对角线被占了。

四、 复杂度分析与建议

• 时间复杂度：$O(N!)$。

  • 第一行有 $N$ 种选法，第二行最多 $N-2$ 种，以此类推。虽然实际剪枝后远小于 $N!$，但在 $N=9$ 时非常轻松。

• 空间复杂度：$O(N^2)$。

  • 主要消耗在于存储棋盘状态和递归深度 $O(N)$。

• 优化建议 (NOI 进阶)：

  • 如果 $N$ 增大到 13-15，布尔数组判断会变慢。此时应学习位运算优化：用三个整数的位（bit）来代表 cols, diag1, diag2 的占用情况，利用按位与、按位异或实现 $O(1)$ 的状态更新和查询。

五、 算法流程图 (C++14 伪代码)

我们通过行递归来实现，这样天然避开了行的冲突。

graph TD
    Start(开始搜索) --> Init(初始化棋盘和三个布尔数组)
    Init --> CallDFS("DFS(当前行 row 等于 0)")

    subgraph DFS_Logic ["递归函数 DFS(row)"]
    CheckBase{"row == n ?"}
    CheckBase -- 是 --> Save(记录当前棋盘并返回)
    CheckBase -- 否 --> LoopInit("循环 col 从 0 到 n-1")
    
    LoopInit --> CheckValid{"当前位置安全吗? 判断 cols, diag1, diag2"}
    CheckValid -- 不安全 --> NextCol(尝试下一个 col)
    CheckValid -- 安全 --> Place("放置皇后: board(row)(col) = 'Q'")
    
    Place --> Update("更新标记: cols, diag1, diag2 设为 true")
    Update --> Recur("递归进入下一行: DFS(row + 1)")
    Recur --> Backtrack("恢复现场: board 改回点, 标记设为 false")
    
    Backtrack --> NextCol
    NextCol -->|循环结束| Return((返回))
    end

    Save --> End(完成)

六、 读题关键词总结

在 NOI 考场上，看到以下词汇应立刻联想 N 皇后模型：

1. “彼此不能相互攻击”：典型的冲突限制搜索。
2. “同一条斜线”：必须立刻在纸上写下 r+c 和 r-c 这两个几何特征。
3. “所有不同的方案”：暗示需要完整遍历搜索树，不能找到一个解就退出。
4. “棋盘方案 (Q 和 .)”：要求在回溯过程中维护一个二维字符矩阵，或在搜索到底部时根据路径记录实时生成。

教练寄语： N 皇后问题是回溯算法的“分水岭”。掌握了如何用 $O(1)$ 的时间判断斜线冲突，你就学会了搜索算法中最核心的优化思想——空间换时间。尝试独立完成 $N=9$ 的代码，如果能进一步研究位运算版，你的搜索功底将会有质的飞跃！加油！