回溯解法思路:
1.用二维char数组来模拟放置皇后操作,同时要先把先将二维数组中全部赋值为'.'来表示空位。
再调用回溯函数 ,终止条件为遍历的行数等于n时结束遍历,把char【】【】类型的值加入到集合li1中,再加加入过程中要将char【】【】类型转化成LIst<String>类型再把li2集合加入到li1集合中去。
2.用for循环来遍历全部的操作,用jiancha()函数检查char【row】【i】节点的同一行和同一列和同一斜线上是否用其他皇后。如果没有,在char【row】【i】放置皇后,再进行递归操作,来代替for嵌套继续遍历下去,结束操作后回溯节点。
class Solution {
//接收最后返回的值
List<List<String>> li1=new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
//声明一个二维数组来进行模拟放皇后的操作
char[][] ch=new char[n][n];
//先将二维数组中全部赋值为'.'来表示空位。
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ch[i][j]='.';
}
}
//调用回溯函数
huisu(ch,0,n);
return li1;
}
//回溯行数
public void huisu(char[][] ch,int row,int n){
//用于接收单个最后符合条件的防置法案
List<String> li2=new ArrayList<>();
//终止条件
if(row==n){
//将char【】【】数组转化加入到集合li2中
for (char[] chars : ch) {
li2.add(new String(chars));
}
//把符合放置法案的加入li1集合中
li1.add(new ArrayList<>(li2));
return ;
}
//进行遍历全部操作
for(int i=0;i<n;i++){
//用jiancha()函数检查char【row】【i】节点的同一行和同一列和同一斜线上是否用其他皇后。
if(jiancha(row,i,n,ch)){
//再char【row】【i】放置皇后操作
ch[row][i]='Q';
//进行递归操作,来代替for嵌套继续遍历下去
huisu(ch,row+1,n);
//结束后,回溯操作
ch[row][i]='.';
}
}
}
//jiancha函数用于检查char【row】【i】节点的同一行和同一列和同一斜线上是否用其他皇后。
public boolean jiancha(int row,int i,int n,char[][] ch){
//检查同一行
for(int k=0;k<n;k++){
if(ch[row][k]=='Q'){
return false;
}
}
//检查同一列
for(int p=0;p<n;p++){
if(ch[p][i]=='Q'){
return false;
}
}
//检查左上方斜线
for(int l=row-1,t=i-1;l>=0&&t>=0;l--,t--){
if(ch[l][t]=='Q'){
return false;
}
}
//检查右上方斜线
for(int a=row-1,b=i+1;a>=0&&b<=n-1;a--,b++){
if(ch[a][b]=='Q'){
return false;
}
}
return true;
}
}