# A concise Java solution using bitmap 0 ms

• 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++;
}
}``````

• can you explain this step? upperlimit = (1 << n) - 1;//"11...11"

• Suppose n=3, (1 << n ) - 1 is 0...01000 - 1 (in binary). Upperlimit's binary value is 0...0111. So the nonzero bits form a row of the checkboard.

• oh, bright, thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.