題目描述
n皇后問題：一個n×n的棋盤恬涧，在棋盤上擺n個皇后穷绵，滿足任意兩個皇后不能在同一行邓馒、同一列或同一斜線上的>方案有多少種嘶朱？
我們知道一個的棋盤，如果標記皇后所在位置為1光酣，不在的位置為0疏遏，那么用二進制表示最為節(jié)省空間。
#include <iostream>
using namespace std;
// ================= 代碼實現(xiàn)開始 =================
//ans:總答案
//allOne：用于二進制&的全1數(shù)
int ans, allOne;
//搜索（用二進制來優(yōu)化）
//pos:其二進制上的某個位置的1表示當前所在行的相應的位置（列）已經(jīng)放了一個皇后
//left:其二進制上的某個位置的1表示當前所在行的相應的位置（是由于右對角線上已經(jīng)有皇后），不能放置皇后
//right：其二進制上的某個位置的1表示當前所在行的相應的位置（是由于左對角線上已經(jīng)優(yōu)皇后）财异，不能放置皇后
void dfs(int pos,int left, int right){
if(pos == allOne){//當且僅當每一列都放了一個皇后下翎，那么整個棋盤已經(jīng)放了n個合法皇后，故要終止
++ans;
return;
}
for(int t = allOne & (~(pos | left | right)); t>0;){//t代表可以放的集合對應的二進制數(shù)
int p = t & -t;//low bit: 二進制中最右邊的1
dfs(pos | p, ((left | p) << 1) & allOne, (right | p) >> 1);
t ^= p;
}
}
//一個n*n的棋盤宝当，在棋盤上擺n個皇后，求滿足任意兩個皇后不能在同一行胆萧，同一列或同一斜線上的方案數(shù)
//n：上述n
//返回值：方案數(shù)
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);
其原理是負數(shù)的補碼為反碼加上1庆揩，加上的1會落在第一個0空位上，這個0空位會恢復到原來的1跌穗，所以取出第一個1
- allone = (1<<n) -1
可以知道1左移n位之后在減去1 得到n個1 用來取出int 所需要的位數(shù) 由n決定订晌。
那么在本體中 pos | left | right 為一行中已經(jīng)放下的位置 那么沒放下的位置都是0 怎么取出空位？
只要~（取反） 然后 用allone &（相與） 再 用lowbit 取出最后一個1 就是可以擺放的位置蚌吸，進行搜索协屡。
和allone 取 & 本來0還是0 本來1還是1 在格子右移出棋盤的時候進行截斷算芯。
