N皇后-二进制剪枝

题目描述
n皇后问题：一个n×n的棋盘，在棋盘上摆n个皇后，满足任意两个皇后不能在同一行、同一列或同一斜线上的>方案有多少种？

我们知道一个的棋盘，如果标记皇后所在位置为1，不在的位置为0，那么用二进制表示最为节省空间。

#include <iostream>
using namespace std;
// ================= 代码实现开始 =================
//ans:总答案
//allOne：用于二进制&的全1数
int ans, allOne;
//搜索（用二进制来优化）
//pos:其二进制上的某个位置的1表示当前所在行的相应的位置（列）已经放了一个皇后
//left:其二进制上的某个位置的1表示当前所在行的相应的位置（是由于右对角线上已经有皇后），不能放置皇后
//right：其二进制上的某个位置的1表示当前所在行的相应的位置（是由于左对角线上已经优皇后），不能放置皇后
void dfs(int pos,int left, int right){
    if(pos == allOne){//当且仅当每一列都放了一个皇后，那么整个棋盘已经放了n个合法皇后，故要终止
        ++ans;
        return;
    }
    for(int t = allOne & (~(pos | left | right)); t>0;){//t代表可以放的集合对应的二进制数
        int p = t & -t;//low bit: 二进制中最右边的1
        dfs(pos | p, ((left | p) << 1) & allOne, (right | p) >> 1);
        t ^= p;
    }
}
//一个n*n的棋盘，在棋盘上摆n个皇后，求满足任意两个皇后不能在同一行，同一列或同一斜线上的方案数
//n：上述n
//返回值：方案数
int getAnswer(int n){
    ans = 0;
    allOne = (1 << n) - 1;
    dfs(0, 0, 0);
    return ans;
}
int main() {
    int n;
    cin >> n;
    cout << getAnswer(n) << endl;
    return 0;
}

其中所运用到的二进制使用方法

• lowbit 取出t中最后一个1

int p = n & (-n);

其原理是负数的补码为反码加上1，加上的1会落在第一个0空位上，这个0空位会恢复到原来的1，所以取出第一个1

• allone = (1<<n) -1
  可以知道1左移n位之后在减去1 得到n个1 用来取出int 所需要的位数 由n决定。
  那么在本体中 pos | left | right 为一行中已经放下的位置 那么没放下的位置都是0 怎么取出空位？
  只要~（取反） 然后 用allone &（相与） 再 用lowbit 取出最后一个1 就是可以摆放的位置，进行搜索。
  和allone 取 & 本来0还是0 本来1还是1 在格子右移出棋盘的时候进行截断。