A slightly different method


  • 0
    L

    A valid N queens configuration is the same as a "valid" permutation of an array of size n. A permutation guarantees that queens wont' be in the same row and same col, we only have to check |a_i - a_j| != |i - j|

    private boolean isValid(List<Integer> conf, int next) {
        int k = conf.size();
        for (int i = 0; i < k; ++i) {
            if (conf.get(i) == next || conf.get(i)-next == k-i || next-conf.get(i) == k-i) {
                return false;
            }
        }
        return true;
    }
    
    private void count(int[] result, List<Integer> conf, int n) {
        if (conf.size() == n) {
            result[0]++;
            return;
        }
        for (int num = 0; num < n; ++num) {
            if (isValid(conf, num)) {
                conf.add(num);
                count(result, conf, n);
                conf.remove(conf.size()-1);
            }
        }
    }
    
    public int totalNQueens(int n) {
        int[] result = new int[1];
        List<Integer> temp = new ArrayList<Integer>();
        count(result, temp, n);
        return result[0];
    }

Log in to reply
 

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