This is part of the "Fastest Solution Ever of N-Queen Problem", using bit mask, beat 90%


  • 0
    public int move(int row, int col, int player) {
            // row: rows[row] |= 1 << col if ((rows[row] ^ K) == 0) win
            // col: cols[col] |= 1 << row if ((cols[col] ^ K) == 0) win
            // pie: if (row + col == n - 1) pie |= (1 << row) if ((pie ^ K) == 0) win
            // na: if (row == col) na |= (1 << row), if ((na ^ K) == 0) win
            int K = (2 << (n - 1)) - 1;
            if (player == 1) {
                rows[row] |= 1 << col;
                cols[col] |= 1 << row;
                if (row + col == n - 1) {
                    pie |= (1 << row);
                }
                if (row == col) {
                    na |= (1 << row);
                }
                
                if ((cols[col] ^ K) == 0 || (rows[row] ^ K) == 0 || (pie ^ K) == 0 || (na ^ K) == 0)
                    return 1;
            } else {
                rows2[row] |= 1 << col;
                cols2[col] |= 1 << row;
                if (row + col == n - 1) {
                    pie2 |= (1 << row);
                }
                if (row == col) {
                    na2 |= (1 << row);
                }
                
                if ((cols2[col] ^ K) == 0 || (rows2[row] ^ K) == 0 || (pie2 ^ K) == 0 || (na2 ^ K) == 0)
                    return 2;
            }
            return 0;
        }
    

Log in to reply
 

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