A concise Java solution using bitmap 0 ms


  • 0
    M

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

  • 0
    Y

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


  • 0
    M

    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.


  • 0
    Y

    oh, bright, thank you!


Log in to reply
 

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