A BITWISE SOLUTION TO THE N-QUEENS PROBLEM IN JAVA (0ms)


  • 0
    E
    public class Solution { 
        //private static int sum = 0; 
        //private static long upperLim = 0; 
        public int totalNQueens(int n) { 
            long upperLim = (1 << n) - 1;
            int[] sum = new int[1];
            
            test(0, 0, 0, upperLim, sum);
            
            return sum[0]; 
        } 
        
        public void test(long row, long ld, long rd, long upperLim, int[] sum) {
            if (row < upperLim) { 
                long pos = (upperLim & (~(row | ld | rd))); 
                while (pos > 0) { 
                    long p = (pos & ((~pos) + 1));
                    pos = pos - p; 
                    test(row+p, ((ld+p) << 1), ((rd+p) >> 1), upperLim, sum); 
                } 
            } 
            else { 
                sum[0]++; 
            } 
        }
    }
    

    Search the title "Bitwise N-Queens" in Google.


Log in to reply
 

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