该问题本质上是经典的 N 皇后问题，要求在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能在同一行、同一列或同一对角线上（包括所有平行于主对角线的线）。题目要求输出所有解（按字典序），并只显示前三个解，最后一行输出解的总数。

核心思路

  1. 问题分析：需要满足三个条件：

    • 每行有且仅有一个皇后。
    • 每列有且仅有一个皇后。
    • 任意两个皇后不在同一对角线（包括两个方向：左上到右下，右上到左下）。

  2. 回溯法（DFS）：

    • 从第 0 行（0-indexed）开始，逐行尝试放置皇后。
    • 对于当前行，尝试每一列，检查该列是否可用，以及两个对角线方向是否冲突。
    • 使用数组记录已占用的列和对角线：
      • vis_col：标记已占用的列。
      • diag1：标记左上到右下的对角线（行 + 列 = 常数）。
      • diag2：标记右上到左下的对角线（行 - 列 + N - 1 = 常数，避免负数下标）。
    • 递归处理下一行，当所有行都放置完毕（到达第 N 行），记录一个有效解。
    • 回溯时，清除当前放置的皇后标记，尝试其他列。

  3. 字典序处理：

    • 按行递归，每行按列从小到大尝试（0 到 N-1），自然生成字典序。
    • 保存前三个有效解，同时统计总解数。

  4. 输出处理：

    • 每个解是 0-indexed 的列位置，输出时需 +1 转换为 1-indexed。
    • 先输出前三个解（每个解占一行，数字空格分隔），最后输出总解数。

代码实现

#include <iostream>
#include <vector>
using namespace std;

int n;
int total = 0;
vector<vector<int>> solutions; // 存储前三个解
vector<int> current;           // 当前解，current[row] = col
vector<bool> vis_col;          // 列占用标记
vector<bool> diag1;            // 对角线1: row + col
vector<bool> diag2;            // 对角线2: row - col + n - 1

void dfs(int row) {
    if (row == n) {
        total++;
        if (total <= 3) {
            solutions.push_back(current);
        }
        return;
    }

    for (int col = 0; col < n; col++) {
        if (vis_col[col] || diag1[row + col] || diag2[row - col + n - 1]) {
            continue;
        }

        // 放置皇后
        current[row] = col;
        vis_col[col] = true;
        diag1[row + col] = true;
        diag2[row - col + n - 1] = true;

        dfs(row + 1);

        // 回溯
        vis_col[col] = false;
        diag1[row + col] = false;
        diag2[row - col + n - 1] = false;
    }
}

int main() {
    cin >> n;

    // 初始化
    current.resize(n);
    vis_col.assign(n, false);
    diag1.assign(2 * n, false); // 大小 2*n 足够（0 到 2n-2）
    diag2.assign(2 * n, false);

    dfs(0);

    // 输出前三个解
    for (int i = 0; i < solutions.size(); i++) {
        for (int j = 0; j < n; j++) {
            if (j > 0) cout << " ";
            cout << solutions[i][j] + 1; // 转换为1-indexed
        }
        cout << endl;
    }

    // 输出总解数
    cout << total << endl;

    return 0;
}

DFS 函数：

  • 终止条件：当 row == n 时，所有行已放置皇后，记录解（若总数 ≤ 3 则保存）。
  • 列尝试：对当前行 row，尝试每一列 col：
    • 检查列 col 和两个对角线（row+col 和 row-col+n-1）是否冲突。
    • 无冲突则放置皇后，标记列和对角线，递归处理下一行。
    • 回溯时清除标记，尝试下一列。

复杂度分析

  • 时间复杂度：O(N!)，最坏情况下需要遍历所有可能的排列。
  • 空间复杂度：O(N)，递归深度和辅助数组大小均为 O(N)。