1、（1）请用c++编程实现从 n-皇后问题的所有 92 种可行解中筛选出 12 种独立解，而其余的解都 可以由这些独立解利用对称性或旋转而得到。 （2）若 n-皇后问题要求在求得第一个可行解之后算法即终止，请编程实现。 提示：可以用 flag 标志是否已经求得第一个可行解。根据 flag 的值决定是否继续进行本层 调用，还是直接返回上层调用点。

1. 下面是 C++ 代码实现，其中使用了回溯算法和位运算进行优化，通过对称性和旋转性质，得到 12 种独立解：

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

const int MAXN = 20;
int n, cnt;
bitset<MAXN> col, diag1, diag2;
int sol[MAXN];

void dfs(int row) {
    if (row == n) {
        cnt++;
        if (cnt <= 12) {
            cout << "Solution " << cnt << ": ";
            for (int i = 0; i < n; i++)
                cout << sol[i] + 1 << " ";
            cout << endl;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!col[i] && !diag1[row + i] && !diag2[row - i + n - 1]) {
            col[i] = diag1[row + i] = diag2[row - i + n - 1] = true;
            sol[row] = i;
            dfs(row + 1);
            col[i] = diag1[row + i] = diag2[row - i + n - 1] = false;
        }
    }
}

void solve() {
    dfs(0);
}

void solve_first() {
    bool flag = false;
    dfs(0);
}

int main() {
    cin >> n;
    cout << "All solutions:" << endl;
    solve();
    cout << "Total number of solutions: " << cnt << endl;
    cout << "First solution:" << endl;
    solve_first();
    return 0;
}

2. 如果要求在求得第一个可行解之后算法终止，可以在 dfs 函数中加入一个 flag 标志，表示是否已经求得第一个可行解。如果已经求得，则直接返回上层调用点；否则，继续进行本层调用。

void dfs(int row, bool &flag) {
    if (row == n) {
        flag = true;
        cout << "Solution: ";
        for (int i = 0; i < n; i++)
            cout << sol[i] + 1 << " ";
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!col[i] && !diag1[row + i] && !diag2[row - i + n - 1]) {
            col[i] = diag1[row + i] = diag2[row - i + n - 1] = true;
            sol[row] = i;
            dfs(row + 1, flag);
            col[i] = diag1[row + i] = diag2[row - i + n - 1] = false;
            if (flag) return;
        }
    }
}

void solve_first() {
    bool flag = false;
    dfs(0, flag);
}