N皇后
题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
//记录每行皇后摆放位置
int[] arr = new int[n];
queen(n,0,arr,ans);
return ans;
}
//判断是否冲突
public static boolean judge(int m,int[] arr){
for(int i=0;i<m;i++){
//判断是否在同一列或者在斜线上
if(arr[i] == arr[m] || Math.abs(m-i) == Math.abs(arr[m] - arr[i])){
return false;
}
}
return true;
}
//递归回溯
public static void queen(int max,int m,int[] arr,List<List<String>> ans){
if(m == max){
String str = "";
List<String> list = new ArrayList<>();
for(int i=0;i<max;i++){
str = "";
for(int j=0;j<max;j++){
if(j == arr[i]){
str+="Q";
}else{
str+=".";
}
}
list.add(str);
}
ans.add(list);
return;
}
for(int i=0;i<max;i++){
//八该皇后放到这一行的第一列
arr[m] = i;
//判断是否冲突
if(judge(m,arr)){
//不冲突继续下一个皇后
queen(max,m+1,arr,ans);
}
}
}
}