作为教练，针对 N 皇后 (N-Queens) 的数据生成与评测，我们需要平衡“全解输出量”与“评测系统压力”。

由于 $n=10$ 时总方案数为 $724$，每种方案 $10 \times 10$ 个字符，加上空格和换行，输出文件约为 $1.5\text{MB}$。这完美符合你要求的 2MB 理想值。如果 $n$ 达到 $12$ 以上，输出文件将突破 $30\text{MB}$，不建议作为“输出所有解”的测试数据。

一、 数据生成器 (gen.cpp)

该生成器使用 C++14 标准，利用位运算（Bitmask）高效生成所有解，并按照测试点规模循环生成 $10$ 组数据。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 高效位运算求解器，用于生成标准输出
int n_val;
int full_mask;
int total_solutions;
vector<vector<string>> all_solutions;
vector<int> queen_pos;

void solve(int row, int col, int ld, int rd) {
    if (col == full_mask) {
        vector<string> board(n_val, string(n_val, '.'));
        for (int i = 0; i < n_val; ++i) {
            board[i][queen_pos[i]] = 'Q';
        }
        all_solutions.push_back(board);
        return;
    }

    int pos = full_mask & ~(col | ld | rd);
    while (pos) {
        int p = pos & -pos;
        pos -= p;

        // 计算当前 p 是第几列
        int c = 0;
        int temp = p >> 1;
        while (temp) { temp >>= 1; c++; }

        queen_pos[row] = c;
        solve(row + 1, col | p, (ld | p) << 1, (rd | p) >> 1);
    }
}

int main() {
    // 测试点 n 规模设计：1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    // 注意：2 和 3 是无解情况的边界测试
    for (int t = 1; t <= 10; ++t) {
        n_val = t;
        full_mask = (1 << n_val) - 1;
        total_solutions = 0;
        all_solutions.clear();
        queen_pos.assign(n_val, 0);

        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";

        // 1. 生成 .in 文件
        ofstream fin(in_name);
        fin << n_val << "\n";
        fin.close();

        // 2. 生成 .out 文件
        solve(0, 0, 0, 0);
        ofstream fout(out_name);
        for (size_t k = 0; k < all_solutions.size(); ++k) {
            for (int i = 0; i < n_val; ++i) {
                for (int j = 0; j < n_val; ++j) {
                    fout << all_solutions[k][i][j] << (j == n_val - 1 ? "" : " ");
                }
                fout << "\n";
            }
            if (k != all_solutions.size() - 1) fout << "\n"; // 方案间的空行
        }
        fout.close();
        cout << "Test Case " << t << " (n=" << n_val << ") generated.\n";
    }
    return 0;
}

二、 特判程序 (checker.cpp)

使用 testlib.h 编写，具备强大的鲁棒性。它会自动跳过多余空格和换行，并使用 seekEof() 严格防止末尾不可见字符导致的错误。

#include "testlib.h"
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

// 验证单一棋盘的合法性
bool checkRules(int n, const vector<string>& board) {
    vector<int> pos;
    for (int i = 0; i < n; ++i) {
        int q_count = 0;
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'Q') {
                pos.push_back(j);
                q_count++;
            }
        }
        if (q_count != 1) return false;
    }
    if ((int)pos.size() != n) return false;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (pos[i] == pos[j]) return false; // 同列
            if (abs(i - j) == abs(pos[i] - pos[j])) return false; // 对角线
        }
    }
    return true;
}

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

    // 1. 获取输入 n
    int n = inf.readInt();

    // 2. 统计标准答案中的解数量
    int ans_count = 0;
    while (!ans.seekEof()) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) ans.readToken();
        }
        ans_count++;
    }

    // 3. 读取并验证选手输出
    set<vector<string>> seen;
    int ouf_count = 0;
    while (!ouf.seekEof()) {
        ouf_count++;
        vector<string> board(n, string(n, ' '));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                string s = ouf.readToken("[Q.]{1}", "cell");
                board[i][j] = s[0];
            }
        }

        // 规则验证
        if (!checkRules(n, board)) {
            quitf(_wa, "Solution #%d violates N-Queens rules", ouf_count);
        }
        // 重复验证
        if (seen.count(board)) {
            quitf(_wa, "Solution #%d is a duplicate", ouf_count);
        }
        seen.insert(board);
    }

    // 4. 数量比对
    if (ouf_count < ans_count) {
        quitf(_wa, "Too few solutions: expected %d, found %d", ans_count, ouf_count);
    }
    if (ouf_count > ans_count) {
        quitf(_wa, "Too many solutions: expected %d, found %d", ans_count, ouf_count);
    }

    // 5. 最终检查文件末尾
    ouf.seekEof(); 
    quitf(_ok, "Correct: Found all %d unique solutions.", ans_count);

    return 0;
}

三、 复杂度与安全性思考 (NOI 竞赛指导)

1. 时间复杂度优化：
   • 生成器使用了 位运算 (Bitmask) 的 N 皇后解法。在 $n=10$ 的规模下，生成全部 10 个测试点仅需几十毫秒。位运算避免了频繁的数组寻址，效率极高。
2. 空间复杂度与防爆栈：
   • 对于 $n=10$，递归深度仅为 $10$ 层，每一层只占用几个 int 的栈空间。即使在内存极小的老旧评测系统上，也绝对不会爆栈。
3. 无除法设计：
   • 代码中仅涉及加减法、位移和位与运算，彻底杜绝了除以 0 的异常 (Exception)。
4. 文件大小控制：
   • $n=10$ 是全解输出的极限平衡点。输出文件约 $1.4\text{MB}$。如果 $n=11$，文件将激增至约 $5\text{MB}$。本设计完美卡在 2MB 理想线内，既能区分算法效率（$n=10$ 对暴力检查有一定压力），又不会导致 OJ 磁盘爆满。
5. SPJ 的鲁棒性：
   • 使用了 ouf.seekEof()。这是最关键的一点，它会先跳过所有空白（换行、空格、\r 等），如果之后没有任何非空字符，才判定为 EOF。这能有效避免因 Windows/Linux 换行符差异（\r\n vs \n）或行末多余空格导致的 Expected EOF 错误。

四、 读题理解关键词总结

做这类搜索题时，教学生抓这些词：

• “所有不同的方案”：意味着不能用贪心，必须用回溯遍历全空间。
• “同一条斜线”：暗示了 $r+c$ 和 $r-c$ 的几何属性。
• “1.0s 时限”：当 $n \ge 13$ 时，位运算是满分的必要条件。
• “任意顺序输出”：暗示后台有 SPJ，不要把时间浪费在手动排序输出结果上。

教练寄语： 同学，N 皇后问题在 $n=10$ 以内是回溯练习，在 $n=15$ 以上是位运算练习，在 $n=10^6$ 时则是构造算法（数学）题。在 NOI 考场上，我们要根据 $n$ 的范围灵活选择武器。这份数据生成方案能帮你夯实最核心的搜索功底！

同学，N 皇后问题在 NOI 竞赛中是考察“搜索剪枝”与“位运算优化”的绝佳题目。虽然 $N=9$ 时普通回溯已足够，但为了让你在省选甚至国赛中更有竞争力，我们需要掌握从基础回溯到位运算极致优化的演进。

版本一：基础回溯（标记数组法）

这是最稳健的写法。利用主副对角线的几何特性（和与差为定值），实现 $O(1)$ 的冲突检查。

思考过程：

• 状态设计：由于每行只能放一个，我们按“行”递归。只需要标记列（col）、主对角线（dg）、副对角线（udg）。
• 对角线索引：
  • 副对角线：$r + c$ 是定值，范围 $[0, 2n-2]$。
  • 主对角线：$r - c$ 是定值，范围 $[-(n-1), n-1]$。为防止负索引，加上偏移量 $n$，即 $r - c + n$。
• 复杂度：时间 $O(N!)$，空间 $O(N^2)$（存储棋盘）。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
vector<string> board;
vector<bool> col, dg, udg;

// depth: 当前处理的行数
void dfs(int r) {
    if (r == n) {
        // 找到一个解，按格式输出
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << board[i][j] << (j == n - 1 ? "" : " ");
            }
            cout << "\n";
        }
        cout << "\n"; // 方案间空行
        return;
    }

    for (int c = 0; c < n; c++) {
        // 关键点：检查列、主对角线、副对角线是否安全
        if (!col[c] && !dg[r - c + n] && !udg[r + c]) {
            board[r][c] = 'Q';
            col[c] = dg[r - c + n] = udg[r + c] = true;
            
            dfs(r + 1);
            
            // 回溯：恢复现场（易错点：标记和棋盘都要改回）
            col[c] = dg[r - c + n] = udg[r + c] = false;
            board[r][c] = '.';
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    if (!(cin >> n)) return 0;

    // 初始化棋盘和标记数组
    board.assign(n, string(n, '.'));
    col.assign(n, false);
    dg.assign(2 * n, false);
    udg.assign(2 * n, false);

    dfs(0);
    return 0;
}

版本二：最优复杂度（位运算优化版）

在 NOI 竞赛中，如果 $N$ 达到 $13 \sim 15$，标记数组的常数开销会导致超时。位运算版是竞赛选手的“杀手锏”。

思考过程：

• 位运算技巧：使用三个整数 col, ld, rd 的位来代表占用情况。
  • col: 列占用。
  • ld: 左对角线占用。下一行时，所有占用位向左移一位（ld << 1）。
  • rd: 右对角线占用。下一行时，所有占用位向右移一位（rd >> 1）。
• 位运算公式：
  • pos = ((1 << n) - 1) & ~(col | ld | rd)：得到所有可放位置。
  • p = pos & -pos：取出最右边的 1（放皇后）。
  • pos &= (pos - 1)：删除最右边的 1。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
int full_mask;
vector<int> queen_pos; // 记录每一行皇后所在的列索引

void dfs(int row_idx, int col, int ld, int rd) {
    if (col == full_mask) {
        // 找到解，根据记录的列索引生成棋盘
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << (j == queen_pos[i] ? "Q" : ".") << (j == n - 1 ? "" : " ");
            }
            cout << "\n";
        }
        cout << "\n";
        return;
    }

    // pos 中位为 1 的表示可以放皇后
    int pos = full_mask & ~(col | ld | rd);
    while (pos) {
        int p = pos & -pos; // 提取最右侧的 1
        pos -= p;           // 放置皇后
        
        // 计算当前皇后在第几列，用于记录路径
        int c = 0;
        int temp = p >> 1;
        while(temp) { temp >>= 1; c++; }
        
        queen_pos[row_idx] = c;
        // 关键点：递归下一行，ld和rd随行数向下而偏移
        dfs(row_idx + 1, col | p, (ld | p) << 1, (rd | p) >> 1);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    if (!(cin >> n)) return 0;

    full_mask = (1 << n) - 1;
    queen_pos.resize(n);

    dfs(0, 0, 0, 0);
    return 0;
}

复杂度分析思考过程

1. 时间复杂度：
   • 理论界限：$O(N!)$。
   • 实际表现：由于每一行、每一列和斜线的约束极其强大，剪枝效率极高。对于 $N=14$，$N! \approx 8.7 \times 10^{10}$，但位运算版可以在 1 秒内跑完。
2. 空间复杂度：
   • 标记数组法：$O(N^2)$，主要用于棋盘字符串存储。
   • 位运算法：$O(N)$，仅需递归栈和存储列索引的数组。

时间复杂度优化建议

1. 利用对称性：N 皇后的棋盘是左右对称的。你可以只搜索第一行的一半位置（如果 $N$ 是奇数，中间一列单独处理），然后将结果镜像翻转。这样可以将搜索量直接减半。
2. 位运算常数：在 NOI Linux 环境下，位运算指令（<<, |, &）是单周期指令，比数组访问（内存寻址）快一个量级。
3. 内联函数与快读：虽然在本题输出才是瓶颈，但养成使用 \n 而非 endl 的习惯能防止在大规模输出时超时。

读题关键词总结

1. “彼此不能相互攻击” $\rightarrow$ 确定冲突规则：行、列、两条对角线。
2. “所有不同的解决方案” $\rightarrow$ 需要搜索全空间，不能使用贪心或剪枝后只留一个解。
3. “n x n 棋盘” $\rightarrow$ 搜索树深度固定为 $n$。
4. “对角线” $\rightarrow$ 核心考点：掌握 $r+c$ 和 $r-c$ 的索引转换。

教练寄语： 同学，N 皇后不仅是回溯法的练手题，它更是你理解“状态压缩”思想的敲门砖。当你能熟练写出位运算版 N 皇后时，你对计算机处理搜索问题的逻辑已经有了质的超越。加油，尝试挑战 $N=13$ 的本地运行速度吧！