回溯困难 LeetCode51. N 皇后

描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

分析

回溯的解法也可以理解为，回溯穷尽了所有n个皇后的放置位置可能结果，对不可能的位置做剪枝。

整个n*n大小的皇后可选位置用n*n的二维字符数组表示，数组方便后面判断可不可以放置"Q"。 递归n层，若当前的层数是n，说明已经递归了n层，要结束了。 每一层都要遍历n个位置，判断可不可以是"Q"

class Solution {
          
   
    List<String> li = new ArrayList<>();
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
          
   
        char[][] queen = new char[n][n];
        backTracking(n,0,queen);
        return res;
    }

    public void backTracking(int n, int row, char[][] queen){
          
   
        if(row == n){
          
   
            res.add(new ArrayList<String>(li));
            return ;
        }
        for(int i = 0; i < n; i++){
          
   
            if(!isAvalible(queen,row,i)){
          
   
                continue;
            }
            queen[row][i] = Q;
            String str = "";
            for(int j = 0; j < n; j++){
          
   
                if(queen[row][j] != Q){
          
   
                    str+=.;
                }else{
          
   
                    str+=Q;
                }
            }
            li.add(str);
            backTracking(n,row+1,queen);
            queen[row][i] = .;
            li.remove(li.size()-1);
        }
    }

    public boolean isAvalible(char[][] queen, int row, int col){
          
   
        for(int i = 0; i < row; i++){
          
   
            if(queen[i][col] == Q){
          
   
                return false;
            }
        }
        for(int i = row, j = col; i >= 0 && j < queen.length; i--,j++){
          
   
            if(queen[i][j] == Q){
          
   
                return false;
            }
        }
        for(int i = row, j = col; i >= 0 && j >= 0; i--,j--){
          
   
            if(queen[i][j] == Q){
          
   
                return false;
            }
        }
        return true;
    }
}