回溯法 | N皇后

class Solution {
    List<List<String>> l = new ArrayList<>();
    int nn ;
    public List<List<String>> solveNQueens(int n) {
        int[] r = new int[n];
        int[] c = new int[n];
        int[] m = new int[2*n];
        int[] q = new int[2*n];
        String[][] dp = new String[n][n];

        nn = n;

        dfs(r,c,m,q,new ArrayList<>(),dp,0,n);

        return l;
    }
    public void dfs(int[] r, int[] c, int[] m, int[] q, List<Integer> res, String[][] dp, int raw,int count){
        if(count==0){
            List<String> rr = fi(dp);
            l.add(new ArrayList<>(rr));
            return;
        }
        
        if( raw>=nn) return;

        for(int i=0;i<nn;i++){
            if(!valid(r,c,q,m,raw,i)) continue;

            dp[raw][i] = "Q";
            c[i] = c[i]+1;
            r[raw] = r[raw]+1;
            q[raw+i] = q[raw+i]+1;
            m[raw-i+nn] = m[raw-i+nn] +1;

            dfs(r,c,m,q,res,dp,raw+1,count-1);

            dp[raw][i] = ".";
            c[i] = c[i]-1;
            r[raw] = r[raw]-1;
            q[raw+i] = q[raw+i]-1;
            m[raw-i+nn] = m[raw-i+nn] -1;
        }

    }
    public boolean valid(int[] r, int[] c, int[] q, int[] m, int raw, int col){
        if(r[raw]!=0) return false;
        if(c[col]!=0) return false;
        if(q[raw+col]!=0) return false;
        if(m[raw-col+nn]!=0) return false;
        return true;
    }
    public List<String> fi(String[][] dp){
        List<String> r = new ArrayList<>();
        for(int i=0;i<dp.length;i++){
            String ss = "";
            for(int j=0;j<dp[0].length;j++){
                if(dp[i][j]==null){
                    dp[i][j] = ".";
                }
               ss = ss+dp[i][j];
            }
            r.add(ss);
        }
        return r;
    }
}