题目描述
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 在格子右移出棋盘的时候进行截断。
