A classic C solution using bitwise operations (0ms)


  • 5
    E

    The code is very short and simple:

    int next(int row, unsigned int vertMask, unsigned int leftMask, unsigned int rightMask, unsigned int rangeMask) {
        if (row == 0)
            return 1;
            
        unsigned int mask = rangeMask & ~(leftMask | rightMask | vertMask);
        int r = 0;
        while (mask) {
            unsigned int queenFlag = mask & -mask;
            r += next(
                    row-1, 
                    (  vertMask | queenFlag ), 
                    (  leftMask | queenFlag ) << 1, 
                    ( rightMask | queenFlag ) >> 1, 
                    rangeMask
                );
            mask ^= queenFlag;
        }
        return r;
    }
    
    int totalNQueens(int n) {
        return next(n, 0, 0, 0, ((unsigned int)-1) >> (32-n));
    }
    

    The main idea is each bit represent a position. If a bit is set to 1, it means this position is unavailable to put a queen into. So with 32-bit integer this way can solve no more than 32-queens problem.

    Assume current is first row, and N == 5. So rangeMask will be 0b 0001 1111.
    This line

    mask = rangeMask & ~(leftMask | rightMask | vertMask)

    make available bits set to 1. So mask = 0b 0001 1111. mask & -mask is a trick to get the lowest 1-bit. Now set a queen at position queenFlag, and try next row.

    Assume row N has a queen at column 3. The arguments for next(N-1, ...) will be:

    To shift left/right queenFlag by 1 will make the positions the queen could attack to set to 1. I set the masks' type to unsigned to avoid signed right shift could cause a bug when N = 32.


  • 0
    K

    Nicely done. I personally think range_mask could be better expressed as (1uL << n) - 1.


Log in to reply
 

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