题解 | #N皇后问题#

import java.util.*;
public class Solution {
   
    List<List<String>> ans = new ArrayList<>();
    int[] row;
    boolean[] cols, d, ud;
    int N;
    public int Nqueen(int n) {
        N = n;
        cols = new boolean[n];
        d = new boolean[25];
        ud = new boolean[25];
        row = new int[n]; // 用来保存第几行第几列放置Q
        dfs(0);
        return ans.size();
    }
    void dfs(int i) { 
        if (i == N) {//行数为n
            char[] arr = new char[N];
            Arrays.fill(arr, '.');
            List<String> tmp = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                arr[row[j]] = 'Q';
                tmp.add(new String(arr)); 
                arr[row[j]] = '.';
            }
            ans.add(tmp);
            return;
        }
        //选择一个位置进行放置
        for (int j = 0; j < N; j++) {
            if (!cols[j] && !d[i + j] && !ud[N - i + j]) {
                //列，对角线、反对角线判断
                cols[j] = d[i + j] = ud[N - i + j]= true;
                row[i] = j;
                dfs(i + 1);
                cols[j] = d[i + j] = ud[N - i + j]= false;
            }
        }
    }
}