文章目录
题目示例代码(回溯)
题目
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例
输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法
代码(回溯)
class Solution {
List
<List
<String>> resultList
= new ArrayList<>();
public List
<List
<String>> solveNQueens(int n
) {
int[] result
= new int[n
];
backTrack(0,n
,result
);
return resultList
;
}
public void backTrack(int row
,int n
,int[] result
){
if(row
== n
){
printResult(result
);
return;
}
for(int col
=0;col
<n
;col
++){
boolean flag
= true;
for(int i
=0;i
<row
;i
++){
if(result
[i
] == col
|| Math
.abs(result
[i
] - col
) == Math
.abs(i
- row
)){
flag
= false;
}
}
if(flag
){
result
[row
] = col
;
backTrack(row
+ 1,n
,result
);
}
}
}
public void printResult(int[] result
){
List
<String> list
= new ArrayList<>();
for(int i
=0;i
<result
.length
;i
++){
StringBuilder sb
= new StringBuilder();
for(int j
=0;j
<result
.length
;j
++){
if(result
[i
] == j
){
sb
.append("Q");
}else{
sb
.append(".");
}
}
list
.add(sb
.toString());
}
resultList
.add(list
);
}
}
参考链接：N皇后 java
