[52. N-Queens II] #leetcode

52_0827.java

class Solution1 {
  // O(n!) O(n)
    private static int[] res;
    private static int count = 0;
    
    public int totalNQueens(int n) {
        if ( n == 0 ) {
            return 1;
        }
        res = new int[n];
        DFS(0, n);
        
        return count;
    }
    
    private static void DFS(int row, int n) {
        for (int col = 0; col < n; col++ ) {
            
            boolean ok = true;
            for (int i = 0; i < row; i++) {
                if (col == res[i] || Math.abs(col - res[i]) == Math.abs(i - row)) {
                    ok = false;
                    break;
                }
            }
            
            if (!ok) continue;
            res[row] = col;
            
            if (row == n - 1) {
                count++;
            } else {
                DFS(row+1, n);
            }
        }
    }
}

class Solution2 {
  // O(n!) O(n)
    private static int count;
    private static boolean[] shu, pie, na;
    
    public int totalNQueens(int n) {
        shu = new boolean[n];
        pie = new boolean[2 * n - 1];
        na = new boolean[2 * n - 1];
        count = 0; 
        
        DFS(0, n);
        
        return count;
    }
    
    private static void DFS(int row, int n) {
        for (int col = 0; col < n; col++ ) {
            int j = row + col;
            int k = n - 1 + col - row;
            
            if (shu[col] || pie[j] || na[k]) continue;

            if (row == n-1) {
                count++;
            }
            else {
                shu[col] = true;
                pie[j] = true;
                na[k] = true;
            
                DFS(row+1, n);
                
                shu[col] = false;
                pie[j] = false;
                na[k] = false;
            }
        }
    }
}

class Solution3 {
  // O(n!) O(n)
    private static int count;
    private static long shu, pie, na;
    
    public int totalNQueens(int n) {
        count = 0; 
        DFS(0, n);
        
        return count;
    }
    
    private static void DFS(int row, int n) {
        for (int col = 0; col < n; col++ ) {
            int j = row + col;
            int k = n - 1 + col - row;
            
            if ((((shu >> col) | 
                (pie >> j) |
                (na >> k)) & 1) != 0) continue;

            if (row == n-1) {
                count++;
            } else {
                shu ^= (1 << col); 
                pie ^= (1 << j);
                na ^= (1 << k);
            
                DFS(row+1, n);
                
                shu ^= (1 << col); 
                pie ^= (1 << j);
                na ^= (1 << k);
            
            }
        }
    }
}

class Solution4 {
  // O(n!) O(n)
    private static int count;
    private static long shu, pie, na;
    
    public int totalNQueens(int n) {
        count = 0; 
        DFS(0, n);
        
        return count;
    }
    
    private static void DFS(int row, int n) {
        long ok =((1 << n) - 1) & ~(shu | (pie >> row) | (na >> (n - 1 - row)));
        
        while (ok != 0){
            long p = ok & -ok;
            ok ^= p;
            
            if (row == n-1) {
                count++;
            } else {
                shu ^= p; 
                pie ^= (p << row);
                na ^= (p << (n-1-row));
            
                DFS(row+1, n);
                
                shu ^= p; 
                pie ^= (p << row);
                na ^= (p << (n-1-row));
            }
        }
    }
}

class Solution5 {
    private static int count;
    
    public int totalNQueens(int n) {
        count = 0; 
        DFS(0, 0, 0, 0, n);
        
        return count;
    }
    
    private static void DFS(int row, long shu, long pie, long na, int n) {
        long ok =((1 << n) - 1) & ~(shu | pie | na);
        
        while (ok != 0){
            long p = ok & -ok;
            ok ^= p;
            
            if (row == n-1) {
                count++;
            } else {
                DFS(row+1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1, n);
            }
        }
    }
}