LeetCode解题笔记 12 —— 51. N皇后
问题
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
解法
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> list = new ArrayList<>();
List<Integer> l = new ArrayList<>();//存放各排皇后放在第几列,比如l.get(0)的值为4即第1排皇后放在第5列
put(list,l,n);
return list;
}
public void put(List<List<String>> list, List<Integer> l, int n){
P:for(int i = 0; i < n; i++){
if(!l.contains(i)){ //该列没有摆放过皇后,继续判断斜线上是否存在皇后
int size = l.size();
for(int k = 0; k < size; k++){
if(size - k == Math.abs(i - l.get(k))){//排数之差 与 列数之差相等 即两个皇后可以互相攻击,故该摆法不行
continue P;
}
}
List<Integer> newList = new ArrayList<>();
newList.addAll(l);
newList.add(i);
if(newList.size() < n){
put(list, newList,n);
}else{
//n个皇后摆放完毕,生成方案并插入
List<String> rList = new ArrayList();
for(Integer index : newList){
StringBuilder b = new StringBuilder();
for(int j=0;j<n;j++){
if(j==index){
b.append("Q");
}else{
b.append(".");
}
}
rList.add(b.toString());
}
list.add(rList);
}
}
}
}
}