按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
解题思路：
从上往下按行依次放置皇后，标记放置过皇后的那一列，后面放皇后不可放在已标记的列上。但如此做，则会有冲突，例如会出现以下情况：
y\x 0 1 2 3
0 皇后 + + + + 皇后 + +
1 + 皇后 + + 皇后 + + +
2 + + 皇后 + + + + 皇后
3 + + + 皇后 + + 皇后 +
但我们会发现：左边第一种情况下，相同左上到右下的斜线上的皇后的y坐标减去x坐标值是相同的；而右边的第二种情况下，相同右上到左下的斜线上的皇后的x坐标加上y坐标值是相同的；
因此我们可以得出结论：当有两个皇后的x,y坐标满足x+y相等或y-x相等时，该摆放方法不成立。
思路理清之后，接下来就可以用回溯的方法遍历，筛选出可行的方案。
class Solution {//创建一个数组放置第i个皇后的位置int queen[][]=new int[10][2];//创建一个数组记录已被占据的列int line[]=new int[10];//创建总返回数组listList<List<String>>list=new ArrayList<>();public List<List<String>> solveNQueens(int n) {List<String> l=new ArrayList<>();backtraver(l,n,0);return list;}//回溯：dfs+for循环public void backtraver(List<String>l,int n,int m){//当数组l大小等于n时表示放置完毕，存入listif(l.size()==n){list.add(new ArrayList<>(l));return;}if(m<n){//for循环遍历每一列for(int x=0;x<n;x++){//访问未被占据的列if(line[x]==0){//判断这一行放的皇后是否会与前面的冲突，若不冲突则放进数组if(isvisit(m,x)){//创建对应要求的String输出char[] row=new char[n];Arrays.fill(row,'.');row[x]='Q';l.add(new String(row));//将该皇后位置放入存放所有皇后位置的数组中queen[m][0]=m;queen[m][1]=x;//将该列置零line[x]=1;//继续回溯backtraver(l,n,m+1);//访问完后退回来将该列置零再将对应元素移除line[x]=0;l.remove(l.size()-1);}}}}}//判断这一行的皇后与前几行的是否冲突public boolean isvisit(int x,int y){if(x==0) return true;for(int z=0;z<x;z++){//若前几行有皇后的y-x或x+y与该皇后相同则返回falseif(queen[z][0]+queen[z][1]==x+y||queen[z][1]-queen[z][0]==y-x)return false;}return true;}
}
