Java easy to understand recursive solution.


  • 1
    C
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ret = new ArrayList<>();
        dfs(n, 0, new int[n], new ArrayList<>(), ret);
        return ret;
    }
    
    private void dfs(int n, int idx, int[] valid, List<String> path, List<List<String>> ret) {
        if (path.size() == n) {
            ret.add(path);
        }
        for (int j = 0; j < n; j++) {
            if (checkValid(valid, idx, j)) {
                valid[idx] = j;
                String s = String.join("", Collections.nCopies(j, "."))+"Q"+
                String.join("", Collections.nCopies(n-j-1, "."));
                List<String> p = new ArrayList<>(path);
                p.add(s);
                dfs(n, idx+1, valid, p, ret);
            }
        }
        
    }
    
    private boolean checkValid(int[] valid, int r, int c) {
        for (int i = 0; i < r; i++) {
            if (valid[i] == c || (r-i) == Math.abs(c-valid[i])) {
                return false;
            }
        }
        return true;
    }

Log in to reply
 

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