用排序树和子集数实现N皇后

下面是使用排序树和子集数实现 N 皇后问题的代码：

#include <iostream>
using namespace std;

const int N = 20;

int n, ans;
int col[N], dia[N], udia[N];  // 分别表示列、正对角线、反对角线是否被占用

void dfs(int u, int state) {
    if (u == n) {  // 找到一组解
        ans++;
        return;
    }
    int available = ((1 << n) - 1) & (~(col[state] | dia[state + u] | udia[n - u + state]));  // 计算可选位置
    while (available) {
        int p = available & -available;  // 取出最右边的 1
        available &= available - 1;  // 将最右边的 1 置为 0
        dfs(u + 1, state | p);  // 继续搜索下一行
    }
}

int main() {
    cin >> n;
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

这个算法的核心思想是使用排序树来遍历所有可能的状态，而不是像普通的搜索算法一样使用回溯。具体来说，我们使用一个二进制数来表示当前已经放置的皇后的位置，其中第 i 位为 1 表示第 i 列已经被占用，第 i 行皇后所在的列号通过 state 中二进制数的第 i 位得到。

在搜索过程中，我们将可选位置计算出来，使用 available 变量来存储可选的位置，每次取出最右边的 1，将其对应的列占用，并继续搜索下一行。