n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例： 输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
依行遍历所有可行的位置，最后一个后放下后再打印地图放入答案列表即可：
class Solution {
public static boolean h1(int[][] loc
,int[] p
,int row
){
for(int i
=0;i
<row
;i
++){
if(loc
[i
][0]==p
[0]||loc
[i
][1]==p
[1]){
return false;
}
if(loc
[i
][0]+loc
[i
][1]==p
[0]+p
[1]){
return false;
}
if(loc
[i
][0]-loc
[i
][1]==p
[0]-p
[1]){
return false;
}
}
return true;
}
public static void h2(int[][] loc
,ArrayList array
,int n
){
char[] ans
=new char[n
];
ArrayList a
=new ArrayList();
for(int i
=0;i
<ans
.length
;i
++){
Arrays
.fill(ans
,'.');
ans
[loc
[i
][1]]='Q';
a
.add(String
.valueOf(ans
));
}
array
.add(a
);
}
public void h3(int n
,int row
,int[][] loc
,ArrayList array
){
int[] p
=new int[2];
for(int i
=0;i
<n
;i
++){
p
[0]=row
;p
[1]=i
;
if(h1(loc
,p
,row
)&&row
!=n
-1){
loc
[row
]=p
;
h3(n
,row
+1,loc
,array
);
}else if(h1(loc
,p
,row
)&&row
==n
-1){
loc
[row
]=p
;
h2(loc
,array
,n
);
}
}
}
public List
<List
<String>> solveNQueens(int n
) {
ArrayList array
=new ArrayList();
int[][] loc
=new int[n
][2];
h3(n
,0,loc
,array
);
return array
;
}
}
