The core idea is to use bitmap to represent the checkboard.

For example, in 4 queens problem, **row** = "0110" means column 1 and 2 in this row is occupied by queens in above rows. **ld** means columns occupied by the left diagonal, and **rd** means columns occupied by the right diagonal.

```
int sum = 0, upperlimit = 1;
public int totalNQueens(int n) {
upperlimit = (1 << n) - 1;//"11...11"
totalNQueens(0, 0, 0);
return sum;
}
void totalNQueens(int row, int ld, int rd) {
int placeable = upperlimit & ~(row | ld | rd);//Get all placeable positions in this row
if (row != upperlimit) {
while (placeable != 0) {
int pos = placeable & (~placeable + 1);//Get the right most placeable position
placeable -= pos;//Remove position from placeable
totalNQueens(row | pos, (ld | pos) << 1, (rd | pos) >> 1); //Get occupied columns of the next row and go to next
}
} else {
sum++;
}
}
```