力扣：51. N 皇后

回溯解法思路：

1.用二维char数组来模拟放置皇后操作，同时要先把先将二维数组中全部赋值为’.’来表示空位。

再调用回溯函数，终止条件为遍历的行数等于n时结束遍历，把char【】【】类型的值加入到集合li1中，再加加入过程中要将char【】【】类型转化成LIst类型再把li2集合加入到li1集合中去。

2.用for循环来遍历全部的操作，用jiancha()函数检查char【row】【i】节点的同一行和同一列和同一斜线上是否用其他皇后。如果没有，在char【row】【i】放置皇后，再进行递归操作，来代替for嵌套继续遍历下去，结束操作后回溯节点。

class Solution {
    //接收最后返回的值
    List<List> li1=new ArrayList();
    public List<List> 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 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=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;
    }
}

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/706889b76a.html

力扣：51. N 皇后

相关推荐