LeetCode: N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

---

Apparently, we can use the same way as the previous problem, and just get the size of the result. Here I introduced another geek solution with the use of bit manipulation. Each row of the board can be treated as a bit array of size n. The basic idea for this approach is also to try every possible solution. The key point is that we can use bit operation to exclude positions that cannot be set to 'Q'. We use 3 variables to represent excluded positions by column, right diagonal, left diagonal. Here is an example:

Assume n is 4 now:

1	1	1	1
0	0	0	0
0	0	0	0
0	0	0	0

For initialization, all elements in the first row is set to 1, which means every position is possible. Assume we try the first spot, Then for the second row, element 0 and element 1 will be set to 1 since they are either in the same column or diagonal with the first row. So row variable for second row is 1000 and right diagonal variable is 0100. Thus we can chose the third spot and the forth spot to try continuously. The table now is:

1	0	0	1
0	0	1	0
0	0	0	0
0	0	0	0

Then for the third row, the row variable is 1010, the right diagonal variable is 0011, the left diagonal variable is 0100. After these three variables make an or operation, we find that there is no available position for now. So we can go back to the second row to try the next candidate. For a better understanding, there are some pictures to illustrate more straight forward in the original blog. Link is at the bottom.

C++ Code:

/*
 * func: total_nqueens_helper
 * goal: helper function for total_nqueens
 * @param column: row check indicator
 * @param left_diagnol: left diagnol indicator
 * @param right_diagnol: right diagnol indicator
 * @param end_flag: flag that indicates one solution found
 * @param result: number of result
 * return:
 */
void total_nqueens_helper(int column, int left_diagonal, int right_diagonal, int end_flag, int &result){
    //binary representations of available spots and currrent spot
    int positions, spot;
    if(column != end_flag){
        //Get all available positions, all impossible spots are set to 1 in three variables
        //with a not operation we can have all possible spots set to 1 for now
        positions = end_flag & (~(column | left_diagonal | right_diagonal));
        while(positions != 0){
            //a & (-a) can be used to get the lowest bit that is 1
            spot = positions & (-positions);
            //Update available spots
            positions = positions - spot;
            //Try for the next row
            total_nqueens_helper(column + spot, (left_diagonal + spot) << 1, (right_diagonal + spot) >> 1, end_flag, result);
        }
    }else{
        ++result;
    }
}
 
/*
 * func: total_nqueens
 * goal: compute the number of total solutions
 * @param n: number of queens
 * return: total number of solutions
 */
int total_nqueens(int n){
    assert(n > 0);
    int result = 0;
    //end flag that indicates one solution was found
    int end_flag = (1 << n)-1;
    total_nqueens_helper(0, 0, 0, end_flag, result);
    return result;
}

Python Code:

class Solution:
    # func: helper function for total_nqueens
    # @param column: bit array of impossible spots based on column
    # @param left_diagonal: bit array of impossible spots based on left_diagonal
    # @param right_diagonal: bit array of impossible spots based on right_diagonal
    # @param end_flag: flag to indicate we have found one solution
    # @return:
    def total_nqueens_helper(self, column, left_diagonal, right_diagonal, end_flag):
        if column != end_flag:
            positions = end_flag & (~(column | left_diagonal | right_diagonal))
            while positions != 0:
                spot = positions & (-positions)
                positions -= spot
                self.total_nqueens_helper(column + spot, (left_diagonal + spot) << 1, (right_diagonal + spot) >> 1, end_flag)
        else:
            self.result += 1

    # func: get the total number of solutions for given nqueens problem
    # @param n: the number of queens
    # @return: the total number
    def total_nqueens(self, n):
        assert n > 0
        self.result = 0
        self.total_nqueens_helper(0, 0, 0, (1 << n)-1)
        return self.result

Reference Link:

1.位运算简介及实用技巧（三）：进阶篇(2) | Matrix67: The Aha Moments:http://www.matrix67.com/blog/archives/266