DFS+回溯法：皇后题（51LC困难）

搜索的过程蕴含了 剪枝 的思想。「剪枝」的依据是：题目中给出的 「N 皇后」 的摆放规则：1、不在同一行；2、不在同一列；3、不在同一主对角线方向上；4、不在同一副对角线方向上。

小技巧：记住已经摆放的皇后的位置
这里记住已经摆放的位置不能像 Flood Fill 一样，简单地使用 visited 布尔数组。放置的规则是：一行一行考虑皇后可以放置在哪一个位置上，某一行在考虑某一列是否可以放置皇后的时候，需要根据前面已经放置的皇后的位置。

由于是一行一行考虑放置皇后，摆放的这些皇后肯定不在同一行，为了避免它们在同一列，需要一个长度为 NN 的布尔数组 cols，已经放置的皇后占据的列，就需要在对应的列的位置标注为 True。

为了保证至少两个皇后不同时出现在 同一主对角线方向 或者 同一副对角线方向。检查策略是，只要「检测」到新摆放的「皇后」与已经摆放好的「皇后」冲突，就尝试摆放同一行的下一个位置，到行尾还不能放置皇后，就退回到上一行。

可以像全排列 used 数组那样，再为 「主对角线（Main diagonal）」 和 「副对角线（Sub diagonal）」 设置相应的 布尔数组变量，只要排定一个 「皇后」 的位置，就需要占住对应的位置。

结合代码加注释：便于复习与分享...

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution{
private int n;
private boolean []col;//记录某一列是否放置皇后
private boolean[]main;//记录某一主对角线是否放置了皇后
private boolean[] sub;//记录副对角线是否放置了皇后
private List<List<String>>res;
  public List<List<String>>solveNQueens(int n){
res=new ArrayList<>();//设置为数组列表
if(n==0){
    return res;
}

//设置成员变量
this.n=n;
this.col=new boolean[n];
this.main=new boolean[2*n-1];
this.sub=new boolean[2*n-1];
Deque<Integer>path=new ArrayDeque<>();//队列，先进先出
dfs(0,path);//开始的行，和队列
return res;
    }

    private void dfs(int row,Deque<Integer>path){
        if(row==n){// 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果
          List<String>board=convert2board(path);
          res.add(board);
          return;//满足上面的row==n，就return，递归结束的条件
        }
        for(int j=0;j<n;j++){// 针对下标为 row 的每一列，尝试是否可以放置
         if(!col[j]&&!main[row-j+n-1]&&!sub[row+j]){//每一列为false（未访问），主（副）对角线找到为false的位置
            path.addLast(j);
            col[j]=true;
            main[row-j+n-1]=true;
            sub[row+j]=true;

            dfs(row+1,path);//等价表达式，行数+1
            main[row-j+n-1]=false;//不满足的就回溯
            sub[row+j]=false;
             col[j]=false;
             path.removeLast();

         }
        }
    }
    private List<String>convert2board(Deque<Integer>path){//用来表示皇后数组的
        List<String>board=new ArrayList<>();
        for(Integer num:path){
           StringBuilder row = new StringBuilder();
            row.append(".".repeat(Math.max(0,n)));
            row.replace(num,num+1,"Q");
            board.add(row.toString());
        }
        return board;
    }
}