力扣——N皇后

class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[] state = new int[n];
        List<List<String>> res = new ArrayList<>();
        eightQu(res, state, 0 , n);
        return res;
    }
    
    private void eightQu(List<List<String>> res,int[] state, int cur,int n) {
        // 递归结束条件
        if (cur == n) {
            List<String> one = new ArrayList<>();
            for (int i = 0; i < state.length; i++) {
                String s = "";
                for (int j = 0; j < state.length; j++) {
                    if (j != state[i]) {
                        s = s + ".";
                    } else {
                        s = s + "Q";
                    }
                }
                one.add(s);
            }
            res.add(one);
            return;
        }


        // 如果行还有没有到8，说明此种解法还未进行完毕
        // 枚举该行的各列，并且判断此列是否合法
        for (int pos = 0; pos < state.length; pos++) {
            state[cur] = pos;
            boolean flag = true;
            // 判断当前列是否合法
            for (int col = 0; col < cur; col++) {
                // 判断和之前已经完成的皇后是否在同列
                boolean sameCol = pos == state[col];
                // 判断和之前已经完成的皇后是否在同一对角线
                boolean sameTri = Math.abs(pos - state[col]) == Math.abs(col - cur);
                if (sameCol || sameTri) {
                    flag = false;
                    break;
                }
            }
            // 如果flag为true，说明当前列合理，递归进入下一个皇后的位置确定
            if (flag) {
                eightQu(res,state,cur + 1,n);
            }
        }
    }
}