[Leetcode][第81题][JAVA][N皇后问题][回溯算法]

傷城~ 2022-12-03 09:59 150阅读 0赞

#### 【问题描述】\[困难\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

###### 1. 主副对角线列 标记 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

**复杂度**  
![在这里插入图片描述][20200903115944572.png_pic_center]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution { 
    
        private int n;
        // 记录某一列是否放置了皇后
        private boolean[] col;
        // 记录主对角线上的单元格是否放置了皇后
        private boolean[] main;
        // 记录了副对角线上的单元格是否放置了皇后
        private boolean[] sub;
        private List<List<String>> res;
    
        public List<List<String>> solveNQueens(int n) { 
            res = new ArrayList<>();
            if (n == 0) { 
                return res;
            }
    
            // 设置成员变量，减少参数传递，具体作为方法参数还是作为成员变量，请参考团队开发规范
            this.n = n;
            this.col = new boolean[n];
            this.main = new boolean[2 * n - 1];
            this.sub = new boolean[2 * n - 1];
            Deque<Integer> path = new ArrayDeque<>();
            dfs(0, path);
            return res;
        }
    
        private void dfs(int row, Deque<Integer> path) { 
            if (row == n) { 
                // 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果
                List<String> board = convert2board(path);
                res.add(board);
                return;
            }
    
            // 针对下标为 row 的每一列，尝试是否可以放置
            for (int j = 0; j < n; j++) { 
                if (!col[j] && !main[row + j] && !sub[row - j + n - 1]) { 
                    path.addLast(j);
                    col[j] = true;
                    main[row + j] = true;
                    sub[row - j + n - 1] = true;
    
                    dfs(row + 1, path);
                    // 递归完成以后，回到之前的结点，需要将递归之前所做的操作恢复
    
                    sub[row - j + n - 1] = false;
                    main[row + j] = false;
                    col[j] = false;
                    path.removeLast();
                }
            }
        }
    
        private List<String> convert2board(Deque<Integer> path) { 
            List<String> board = new ArrayList<>();
            for (Integer num : path) { 
                StringBuilder row = new StringBuilder();
                row.append(".".repeat(Math.max(0, n)));
                row.replace(num, num + 1, "Q");
                board.add(row.toString());
            }
            return board;
        }
    }

其实已经摆放皇后的列下标、占据了哪一条主对角线、哪一条副对角线也可以使用哈希表来记录。

**实际上哈希表底层也是数组，使用哈希表可以不用处理已经占据位置的皇后的主对角线、副对角线的下标偏移问题。**

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    public class Solution { 
    
        private Set<Integer> col;
        private Set<Integer> main;
        private Set<Integer> sub;
        private int n;
        private List<List<String>> res;
    
        public List<List<String>> solveNQueens(int n) { 
            this.n = n;
            res = new ArrayList<>();
            if (n == 0) { 
                return res;
            }
    
            col = new HashSet<>();
            main = new HashSet<>();
            sub = new HashSet<>();
    
            Deque<Integer> path = new ArrayDeque<>();
            dfs(0, path);
            return res;
        }
    
        private void dfs(int row, Deque<Integer> path) { 
            if (row == n) { 
                List<String> board = convert2board(path);
                res.add(board);
                return;
            }
    
            // 针对每一列，尝试是否可以放置
            for (int i = 0; i < n; i++) { 
                if (!col.contains(i) && !main.contains(row + i) && !sub.contains(row - i)) { 
                    path.addLast(i);
                    col.add(i);
                    main.add(row + i);
                    sub.add(row - i);
    
                    dfs(row + 1, path);
    
                    sub.remove(row - i);
                    main.remove(row + i);
                    col.remove(i);
                    path.removeLast();
                }
            }
        }
    
        private List<String> convert2board(Deque<Integer> path) { 
            List<String> board = new ArrayList<>();
            for (Integer num : path) { 
                StringBuilder row = new StringBuilder();
                row.append(".".repeat(Math.max(0, n)));
                row.replace(num, num + 1, "Q");
                board.add(row.toString());
            }
            return board;
        }
    }

###### 2. board\[n\]\[n\]标记 直接遍历 ######

**时间复杂度：O(N!) 空间复杂度：O(N2)**

class Solution { 
        List<List<String>> res=new ArrayList<>();
        public List<List<String>> solveNQueens(int n) { 
            //棋盘,默认为0表示空，1表示皇后
            int[][] borad = new int[n][n];
            //row当前填写得的行号
            dfs(n,0,borad);
    
            return res;
           
                 
        }
    
        public void dfs(int n,int row,int[][] board) {  
           
            if (row == n) {  
                // n个棋子都放置好了，打印结果 
                res.add(track(board,n));
                // n行棋子都放好了，已经没法再往下递归了，所以就return } 
                 return; 
            }
                 
                 for (int column = 0; column < n; ++column) {  
                     // 每一行都有8中放法 
                     if (isOk(row, column,n,board)) {  // 有些放法不满足要求 
                          board[row][column] =1; 
                          dfs( n,row+1,board); // 考察下一行
                          board[row][column] =0;
                    } 
                }
               
            }
    
        private boolean isOk(int row ,int column ,int n,int[][] board){ 
            int leftup = column -1,rightup = column+1;
            for(int i=row-1;i>=0;i--){ // 逐行往上考察每一行
                if(board[i][column]==1){ // 第i行的column列有棋子吗？
                    return false;
                }
                if(leftup>=0){ // 考察左上对角线：第i行leftup列有棋子吗？
                    if(1==board[i][leftup])
                        return false;
                }
                if(rightup<n){ // 考察右上对角线：第i行rightup列有棋子吗？
                      if(1==board[i][rightup])
                        return false;
                    }
                 leftup--;
                rightup++;
            }
                 return true;
        }
          
        private List<String> track(int[][] board, int n) { // 打印出一个二维矩阵
             List<String> list=new ArrayList<>();
              for (int row = 0; row < n; ++row) {  
                 StringBuffer str = new StringBuffer();
                for (int column = 0; column < n; ++column) {  
                    if (board[row][column] == 1){ 
                        str.append("Q");
                    }else{ 
                        str.append(".");
                    } 
                }
                list.add(str.toString());
            } 
            return list;
        }
    }

#### 【总结】 ####

###### 1.回溯模板 ######

List<> res = new LinkedList<>();
    Deque<Integer> path =  new ArrayDeque<>();
    
    void dfs(路径, 选择列表){
        if 满足结束条件{
            res.add(路径);
            return;
        }
    
        for 选择 in 选择列表{
            // 做选择;
            // 标记一下已经选了，有些题目不需要标记
            nums[i] = true;
            // 把选择的放进路径
            path.push(i)
            dfs(路径, 选择列表);
            
            // 恢复现场;
            path.pop();
            nums[i] = false;
        }
    }

###### 2.回溯思想 ######

[【数据结构与算法】【算法思想】回溯算法][Link 1]

转载链接：https://leetcode-cn.com/problems/n-queens/solution/gen-ju-di-46-ti-quan-pai-lie-de-hui-su-suan-fa-si-/  
转载链接：https://leetcode-cn.com/problems/n-queens/solution/java-hui-su-xiang-xi-zhu-jie-bu-tong-fang-fa-pan-d/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9d597749a0dd4d2b84ddd218df514954.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/0edef8e06a344ef9a72e01919cbcd212.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/f29d8381e8db4b269c5fbffcd3245811.png
[20200903115944572.png_pic_center]: /images/20221123/bf44aabe528c4aad8e6d0546226940f5.png
[Link 1]: https://blog.csdn.net/dadongwudi/article/details/108242926