题意概括

N 皇后问题要求在一个 $n \times n$ 的棋盘上放置 $n$ 个皇后，并使其互相不能攻击。皇后的攻击范围包括其所在的同一行、同一列以及两条对角线。你需要找出所有不同的解决方案，并按照指定格式输出棋盘布局。

数据范围:

• $1 \le n \le 9$

基础知识

N 皇后问题是 回溯法 (Backtracking) 的一个典范应用，通常通过 深度优先搜索 (DFS) 实现。

解决这个问题的基本思路是逐行放置皇后。因为规则规定每行只能有一个皇后，我们可以设计一个递归函数 dfs(r)，其功能是在棋盘的第 r 行放置一个皇后。

1. 递归函数 dfs(r)：
   • 终止条件：当 r == n 时，说明我们已经成功地在 0 到 n-1 行都放置了皇后，找到了一个完整的解决方案。此时，我们保存或打印当前的棋盘布局。
   • 遍历与剪枝：在第 r 行，我们从第 0 列开始，依次尝试到第 n-1 列。对于每一个尝试的列 c，我们需要判断在 (r, c) 位置放置皇后是否会与之前（第 0 到 r-1 行）的皇后冲突。
   • 递归深入：如果位置 (r, c) 是安全的，我们就在该位置“放置”皇后，并递归调用 dfs(r + 1) 来解决下一行的问题。
   • 回溯：当从 dfs(r + 1) 的调用返回后，我们需要“撤销”在 (r, c) 位置的放置，以便在第 r 行的下一个可用列 c+1 上继续尝试。这个“撤销”操作就是回溯的核心。

冲突判断优化： 每次都遍历之前的行来判断冲突效率较低。我们可以使用额外的空间来记录哪些列和对角线已经被占据，从而实现 $O(1)$ 的冲突判断。

• 列：用一个布尔数组 col[c] 记录第 c 列是否被占用。
• 正对角线：同一条正对角线（左上到右下）上的所有格子 (r, c)，其行列之差 r - c 是一个常数。我们可以用 udg[r - c] 来标记。
• 反对角线：同一条反对角线（右上到左下）上的所有格子 (r, c)，其行列之和 r + c 是一个常数。我们可以用 dg[r + c] 来标记。 (注意：r - c 可能是负数，在用作数组索引时需要加上一个偏移量，如 n)。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int n;
int cnt; // 解决方案计数器
vector<string> b; // 棋盘
vector<bool> col, dg, udg;

void dfs(int r) {
    // 如果成功放完 n 行，则找到一个解
    if (r == n) {
        cout << "Solution " << ++cnt <<":"<< endl;
        for (int i = 0; i < n; ++i) {
            cout << b[i] << endl;
        }
        cout << endl;
        return;
    }

    // 遍历当前行的每一列
    for (int c = 0; c < n; ++c) {
        // 剪枝：判断(r, c)是否与之前的皇后冲突
        if (!col[c] && !dg[r + c] && !udg[c - r + n]) {
            // 放置皇后
            b[r][c] = 'Q';
            col[c] = dg[r + c] = udg[c - r + n] = true;

            // 递归到下一行
            dfs(r + 1);

            // 回溯，撤销放置
            col[c] = dg[r + c] = udg[c - r + n] = false;
            b[r][c] = '.';
        }
    }
}

void run() {
    cin >> n;

    cnt = 0;
    b.assign(n, string(n, '.'));
    col.assign(n, false);
    dg.assign(2 * n, false);  // r+c 的范围是 0 到 2n-2
    udg.assign(2 * n, false); // c-r+n 的范围是 1 到 2n-1

    dfs(0);
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
4
输出:
Solution 1
.Q..
...Q
Q...
..Q.

Solution 2
..Q.
Q...
...Q
.Q..

*/