Day37——回溯专题

电玩女神 2024-03-31 11:15 98阅读 0赞

#### 文章目录 ####

*   *   *  14.N皇后
         *  15.解数独

--------------------

#### 14.N皇后 ####

**思路**：

首先来看一下皇后们的约束条件：

1.  不能同行
2.  不能同列
3.  不能同斜线

**回溯三部曲**

**模板**

void dfs(参数) {
        
        if (终止条件) {
        
            存放结果;
            return;
        }
        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        
            处理节点;
            dfs(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }

*  递归函数参数

public void dfs(int n,int row,char[][] chessboard){
        
     }

*  递归终止条件

![image-20221124205733338][]

if(row==n){
        
                res.add(ArrayList2(chessboard));
                return;
            }

*  单层搜索的逻辑

递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。

每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

for(int col = 0;col<n;col++){
        
                if(isValid(row,col,n,chessboard)){
        
                    chessboard[row][col] = 'Q';
                    dfs(n,row+1,chessboard);
                    chessboard[row][col] = '.';
                }

*  验证棋盘是否合法

**按照如下标准去重**：

1.  不能同行
2.  不能同列
3.  不能同斜线 （45度和135度角）

public boolean isValid(int row,int col,int n,char[][] chessboard){
        
            for(int i=0;i<row;i++){
        
                if(chessboard[i][col]=='Q'){
        
                    return false;
                }
            }
            for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
        
                if(chessboard[i][j]=='Q'){
        
                    return false;
                }
            }
            for(int i=row-1,j=col+1;i>=0&&j<=n-1;i--,j++){
        
                if(chessboard[i][j]=='Q'){
        
                    return false;
                }
            }
            return true;
        }

**Code**

class Solution {
        
        List<List<String>> res = new ArrayList<>();
        public List<List<String>> solveNQueens(int n) {
        
            char[][] chessboard = new char[n][n];
            for(char[] c : chessboard){
        
                Arrays.fill(c,'.');
            }
            dfs(n,0,chessboard);
            return res;
        }
        public void dfs(int n,int row,char[][] chessboard){
        
            if(row==n){
        
                res.add(ArrayList2(chessboard));
                return;
            }
            for(int col = 0;col<n;col++){
        
                if(isValid(row,col,n,chessboard)){
        
                    chessboard[row][col] = 'Q';
                    dfs(n,row+1,chessboard);
                    chessboard[row][col] = '.';
                }
            }
        }
        public List ArrayList2(char[][] chessboard){
        
            List<String> list = new ArrayList<>();
            for(char[] c : chessboard){
        
                list.add(String.copyValueOf(c));
            }
            return list;
        }
        public boolean isValid(int row,int col,int n,char[][] chessboard){
        
            for(int i=0;i<row;i++){
        
                if(chessboard[i][col]=='Q'){
        
                    return false;
                }
            }
            for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
        
                if(chessboard[i][j]=='Q'){
        
                    return false;
                }
            }
            for(int i=row-1,j=col+1;i>=0&&j<=n-1;i--,j++){
        
                if(chessboard[i][j]=='Q'){
        
                    return false;
                }
            }
            return true;
        }
    }

#### 15.解数独 ####

**思路**：

![image-20221124213422240][]

**回溯三部曲**

*  递归函数以及参数

private boolean dfs(char[][] board){
        
    }

*  递归终止条件

本题不需要终止条件，等数组填满之后，自然就终止了。

*  递归单层搜索逻辑

for (int i = 0; i < 9; i++){
         // 遍历行
                for (int j = 0; j < 9; j++){
         // 遍历列
                    if (board[i][j] != '.'){
         // 跳过原始数字
                        continue;
                    }
                    for (char k = '1'; k <= '9'; k++){
         // (i, j) 这个位置放k是否合适
                        if (isValidSudoku(i, j, k, board)){
        
                            board[i][j] = k;
                            if (dfs(board)){
         // 如果找到合适一组立刻返回
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    // 9个数都试完了，都不行，那么就返回false
                    return false;
                    // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                    // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
                }
            }
            // 遍历完没有返回false，说明找到了合适棋盘位置了
            return true;
        }

*  判断棋盘是否合法

private boolean isValidSudoku(int row, int col, char val, char[][] board){
        
            // 同行是否重复
            for (int i = 0; i < 9; i++){
        
                if (board[row][i] == val){
        
                    return false;
                }
            }
            // 同列是否重复
            for (int j = 0; j < 9; j++){
        
                if (board[j][col] == val){
        
                    return false;
                }
            }
            // 9宫格里是否重复
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            for (int i = startRow; i < startRow + 3; i++){
        
                for (int j = startCol; j < startCol + 3; j++){
        
                    if (board[i][j] == val){
        
                        return false;
                    }
                }
            }
            return true;
        }

**Code**

class Solution {
        
        public void solveSudoku(char[][] board) {
        
            dfs(board);
        }
    
        private boolean dfs(char[][] board){
        
            //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
            // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
            for (int i = 0; i < 9; i++){
         // 遍历行
                for (int j = 0; j < 9; j++){
         // 遍历列
                    if (board[i][j] != '.'){
         // 跳过原始数字
                        continue;
                    }
                    for (char k = '1'; k <= '9'; k++){
         // (i, j) 这个位置放k是否合适
                        if (isValidSudoku(i, j, k, board)){
        
                            board[i][j] = k;
                            if (dfs(board)){
         // 如果找到合适一组立刻返回
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    // 9个数都试完了，都不行，那么就返回false
                    return false;
                    // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                    // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
                }
            }
            // 遍历完没有返回false，说明找到了合适棋盘位置了
            return true;
        }
    
        /**
         * 判断棋盘是否合法有如下三个维度:
         *     同行是否重复
         *     同列是否重复
         *     9宫格里是否重复
         */
        private boolean isValidSudoku(int row, int col, char val, char[][] board){
        
            // 同行是否重复
            for (int i = 0; i < 9; i++){
        
                if (board[row][i] == val){
        
                    return false;
                }
            }
            // 同列是否重复
            for (int j = 0; j < 9; j++){
        
                if (board[j][col] == val){
        
                    return false;
                }
            }
            // 9宫格里是否重复
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            for (int i = startRow; i < startRow + 3; i++){
        
                for (int j = startCol; j < startCol + 3; j++){
        
                    if (board[i][j] == val){
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

[image-20221124205733338]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/861ca61c2d6446c4b236c4bcedc50cf6.png
[image-20221124213422240]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bc88eaaf861c443698945db4f1527098.png