N皇后
N皇后问题
http://www.nowcoder.com/questionTerminal/c76408782512486d91eea181107293b6
思路
- 列,对角线,斜对角线是否可放棋子分别用二进制数表示
- 每次枚举可放棋子的列,使用lowbit运算
参考链接
https://zhuanlan.zhihu.com/p/22846106
class Solution { private: int cnt = 0; int col; int dg; int udg; map<int, int> mp; public: /** * * @param n int整型 the n * @return int整型 */ int lowbit(int x){ return x & -x; } void dfs(int x, int &n){ int avail = col & (dg >> x) & (udg >> (n-x)); for(int y=avail;y;y -= lowbit(y)){ if(x == n-1) cnt++; else{ int t = mp[lowbit(y)]; col -= 1 << t; dg -= 1 << (x + t); udg -= 1 << (t - x + n); dfs(x+1, n); col += 1 << t; dg += 1 << (x + t); udg += 1 << (t - x + n); } } } int Nqueen(int n) { for(int i=0;i<n;i++) mp[1 << i] = i; col = (1 << n) - 1; dg = udg = (1 << (2*n)) - 1; dfs(0, n); return cnt; } };