回溯法:LeetCode:51. N 皇后问题

解题思路

最开始写理解错了,注意！！！(N皇后要求的是所在的列和行,以及斜方向上都不存在其他皇后) 我们需要将皇后一层一层的探索尝试,判断其是否在当前位置上能够放置 并且在一次完成后需要对现场进行恢复 如果觉得理解起来有点困难的话,可以尝试着先对皇后排列情况进行穷举,不考虑其要求，然后在这样的基础上，再去进行修改，相信大家就都能理解并且掌握这道题目了

代码

class Solution {
          
   
    List<List<String>> ans;
    String[][] map;
    public List<List<String>> solveNQueens(int n) {
          
   
        ans = new ArrayList<>();
        map = new String[n][n];
        for (int i=0;i<n;i++){
          
   
            for (int j=0;j<n;j++){
          
   
                map[i][j]=".";
            }
        }
        LinkedList<String> road = new LinkedList<>();
        backtrack(0,n,road);
        return ans;
    }
    //进行搜索和回溯
    public void backtrack(int row, int n, LinkedList<String> road){
          
   
        //1.终止条件
        if (road.size()==n){
          
   
            ans.add(new LinkedList<>(road));
            return;
        }
        for(int i=0;i<n;i++){
          
   
            //2.尝试放置
            if (judge(row,i,n)) map[row][i]="Q";
            else continue;
            String string = "";
            for (int j=0;j<n;j++){
          
   
                string+=map[row][j];
            }
            road.add(string);
            //3.继续递归
            backtrack(row+1, n, road);
            //4.状态恢复
            map[row][i]=".";
            road.removeLast();
        }
    }
    //判断皇后是否被攻击
    public boolean judge(int x,int y,int n){
          
   
        for (int i=x,j=0;j<n;j++){
          
   
            if (map[i][j].equals("Q")) return false;
        }
        for (int i=y,j=0;j<n;j++){
          
   
            if (map[j][i].equals("Q")) return false;
        }
        for (int i=x,j=y;i<n&&j<n;i++,j++){
          
   //右下斜
            if (map[i][j].equals("Q")) return false;
        }
        for (int i=x,j=y;i>=0&&j<n;i--,j++){
          
   //右上斜
            if (map[i][j].equals("Q")) return false;
        }
        for (int i=x,j=y;i<n&&j>=0;i++,j--){
          
   //左下斜
            if (map[i][j].equals("Q")) return false;
        }
        for (int i=x,j=y;i>=0&&j>=0;i--,j--){
          
   //左上斜
            if (map[i][j].equals("Q")) return false;
        }
        return true;
    }
}