37. 解数独

桃扇骨 2023-10-16 14:52 13阅读 0赞

#### 37.解数独 ####

*  题干描述
 *  解题思路
 *  回溯三部曲
 *   *  1. 递归函数以及参数
     *  2. 递归终止
     *  3. 递归单层搜索逻辑
     *   *  判断棋盘是否合法
 *  总结
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]  
编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。  
![在这里插入图片描述][f348bf2e0fd04a99b5c1d8ec68639bad.png]  
一个数独。  
![在这里插入图片描述][a1b8fd3a178d4dde81d519991ff05c24.png]  
答案被标成红色。

提示：

*  给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
 *  你可以假设给定的数独只有唯一解。
 *  给定数独永远是 9x9 形式的。

## 解题思路 ##

棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是**二维递归**。

怎么做二维递归呢？

77.组合（组合问题），131.分割回文串（分割问题），78.子集（子集问题） ，46.全排列（排列问题），以及51.N皇后（N皇后问题），其实这些题目都是一维递归。

**N皇后问题**是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，**本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深**。

因为这个树形结构太大了，我抽取一部分，如图所示：  
![在这里插入图片描述][391e2fcd0ca7429fa8523b591fbb9826.png]

## 回溯三部曲 ##

### 1. 递归函数以及参数 ###

**递归函数的返回值需要是bool类型，为什么呢？**

因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。

### 2. 递归终止 ###

本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。

**不用终止条件会不会死循环？**

递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！

**那么有没有永远填不满的情况呢？**  
这个问题的答案在递归单层搜索逻辑里！

### 3. 递归单层搜索逻辑 ###

![在这里插入图片描述][609aac9e3f2b40d5b25360b259d445da.png]  
在树形图中可以看出我们需要的是一个二维的递归（也就是两个for循环嵌套着递归）

**一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！**

因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！

那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！

#### 判断棋盘是否合法 ####

判断棋盘是否合法有如下三个维度：

*  同行是否重复
 *  同列是否重复
 *  9宫格里是否重复

## 总结 ##

解数独可以说是非常难的题目了，如果还一直停留在单层递归的逻辑中，这道题目可以让大家瞬间崩溃。

所以我在开篇就提到了二维递归，这也是代码随想录Carl老师自创词汇，希望可以帮助大家理解解数独的搜索过程。

一波分析之后，再看代码会发现其实也不难，唯一难点就是理解二维递归的思维逻辑。

## 代码实现 ##

class Solution {
        
        // 37.解数独
        public void solveSudoku(char[][] board){
        
            solveSudokuHelper(board);
        }
    
        private boolean solveSudokuHelper(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(solveSudokuHelper(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;
        }
    }

**参考资料**：[代码随想录-37.解数独][-37.]

[Link 1]: https://leetcode.cn/problems/sudoku-solver/
[f348bf2e0fd04a99b5c1d8ec68639bad.png]: https://img-blog.csdnimg.cn/f348bf2e0fd04a99b5c1d8ec68639bad.png
[a1b8fd3a178d4dde81d519991ff05c24.png]: https://img-blog.csdnimg.cn/a1b8fd3a178d4dde81d519991ff05c24.png
[391e2fcd0ca7429fa8523b591fbb9826.png]: https://img-blog.csdnimg.cn/391e2fcd0ca7429fa8523b591fbb9826.png
[609aac9e3f2b40d5b25360b259d445da.png]: https://img-blog.csdnimg.cn/609aac9e3f2b40d5b25360b259d445da.png
[-37.]: https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE