题目
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
所有结果都能列出来，那么个数当然能数出来，思路和N-Queens中一致，不再赘述。这里给出一种比较凶残的解法：用比特位运算来纪录皇后的占用位置，具体思路写在注释里。
代码
public class NQueensII {
/* backtrace program using bit-wise operation to speed up calculation.
* 'limit' is all '1's.
* 'h' is the bits all the queens vertically projected on a row. If h==limit, then it's done, answer++.
* 'r' is the bits all the queens anti-diagonally projected on a row.
* 'l' is the bits all the queens diagonally projected on a row.
* h|r|l is all the occupied bits. Then pos = limit & (~(h|r|l)) is all the free positions.
* p = pos & (-pos) gives the right most '1'. pos -= p means we will place a queen on this bit
* represented by p.
* 'h+p' means one more queue vertically projected on next row.
* '(r+p)<<1' means one more queue anti-diagonally projected on next row. Because we are
* moving to next row and the projection is skew from right to left, we have to
* shift left one position after moved to next row.
* '(l+p)>>1' means one more queue diagonally projected on next row. Because we are
* moving to next row and the projection is skew from left to right, we have to
* shift right one position after moved to next row.
*/
private int ans, limit;
public int totalNQueens(int n) {
ans = 0;
limit = (1 << n) - 1;
dfs(0, 0, 0);
return ans;
}
void dfs(int h, int r, int l) {
if (h == limit) {
ans++;
return;
}
int pos = limit & (~(h | r | l));
while (pos > 0) {
int p = pos & (-pos);
pos -= p;
dfs(h + p, (r + p) << 1, (l + p) >> 1);
}
}
}