0ms C++ solution use bit method


  • 0
    A

    a faster method use bit than backtracking
    row:8-bits int variable like 11010100 means position 1\2\4\6 has queen ,so we can only consider the position 3\5\7\8
    main: main diag
    anti : anti diag

    class Solution {
    public:
    
    void queenBit(int row,int main,int anti,const int all_queen)
    {
        if(row!=all_queen)
        {
            int pos = all_queen & ~(row|main|anti);
            while(pos!=0)
            {
                int p = pos&-pos;
                pos-=p;
                queenBit(row+p,(main+p)<<1,(anti+p)>>1,all_queen);
            }
        }
        else
        {
            res++;
            return ;
        }
    }
    
    int totalNQueens(int n) {
        
        res = 0;
    	int all_queen = (1<<n)-1;
    	queenBit(0,0,0,all_queen);
        return res;
    }
    private:
        int res;
    
    };
    

Log in to reply
 

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