1 Star 0 Fork 8

muhao_1019/leetcode-master

forked from 东圣/leetcode-master 
加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
pics
problems
前序
周总结
0001.两数之和.md
0015.三数之和.md
0017.电话号码的字母组合.md
0018.四数之和.md
0019.删除链表的倒数第N个节点.md
0020.有效的括号.md
0024.两两交换链表中的节点.md
0027.移除元素.md
0028.实现strStr.md
0035.搜索插入位置.md
0037.解数独.md
0039.组合总和.md
0040.组合总和II.md
0045.跳跃游戏II.md
0046.全排列.md
0047.全排列II.md
0051.N皇后.md
0053.最大子序和.md
0053.最大子序和(动态规划).md
0055.跳跃游戏.md
0056.合并区间.md
0059.螺旋矩阵II.md
0062.不同路径.md
0063.不同路径II.md
0070.爬楼梯.md
0070.爬楼梯完全背包版本.md
0072.编辑距离.md
0077.组合.md
0077.组合优化.md
0078.子集.md
0090.子集II.md
0093.复原IP地址.md
0096.不同的二叉搜索树.md
0098.验证二叉搜索树.md
0101.对称二叉树.md
0102.二叉树的层序遍历.md
0104.二叉树的最大深度.md
0106.从中序与后序遍历序列构造二叉树.md
0108.将有序数组转换为二叉搜索树.md
0110.平衡二叉树.md
0111.二叉树的最小深度.md
0112.路径总和.md
0115.不同的子序列.md
0121.买卖股票的最佳时机.md
0122.买卖股票的最佳时机II.md
0122.买卖股票的最佳时机II(动态规划).md
0123.买卖股票的最佳时机III.md
0131.分割回文串.md
0134.加油站.md
0135.分发糖果.md
0139.单词拆分.md
0142.环形链表II.md
0150.逆波兰表达式求值.md
0151.翻转字符串里的单词.md
0188.买卖股票的最佳时机IV.md
0198.打家劫舍.md
0202.快乐数.md
0203.移除链表元素.md
0206.翻转链表.md
0209.长度最小的子数组.md
0213.打家劫舍II.md
0216.组合总和III.md
0222.完全二叉树的节点个数.md
0225.用队列实现栈.md
0226.翻转二叉树.md
0232.用栈实现队列.md
0235.二叉搜索树的最近公共祖先.md
0236.二叉树的最近公共祖先.md
0239.滑动窗口最大值.md
0242.有效的字母异位词.md
0257.二叉树的所有路径.md
0279.完全平方数.md
0300.最长上升子序列.md
0309.最佳买卖股票时机含冷冻期.md
0322.零钱兑换.md
0332.重新安排行程.md
0337.打家劫舍III.md
0343.整数拆分.md
0344.反转字符串.md
0347.前K个高频元素.md
0349.两个数组的交集.md
0376.摆动序列.md
0377.组合总和Ⅳ.md
0383.赎金信.md
0392.判断子序列.md
0404.左叶子之和.md
0406.根据身高重建队列.md
0416.分割等和子集.md
0435.无重叠区间.md
0450.删除二叉搜索树中的节点.md
0452.用最少数量的箭引爆气球.md
0454.四数相加II.md
0455.分发饼干.md
0459.重复的子字符串.md
0474.一和零.md
0491.递增子序列.md
0494.目标和.md
0501.二叉搜索树中的众数.md
0509.斐波那契数.md
0513.找树左下角的值.md
0516.最长回文子序列.md
0518.零钱兑换II.md
0530.二叉搜索树的最小绝对差.md
0538.把二叉搜索树转换为累加树.md
0541.反转字符串II.md
0583.两个字符串的删除操作.md
0617.合并二叉树.md
0647.回文子串.md
0654.最大二叉树.md
0669.修剪二叉搜索树.md
0674.最长连续递增序列.md
0700.二叉搜索树中的搜索.md
0701.二叉搜索树中的插入操作.md
0704.二分查找.md
0707.设计链表.md
0714.买卖股票的最佳时机含手续费.md
0714.买卖股票的最佳时机含手续费(动态规划).md
0718.最长重复子数组.md
0738.单调递增的数字.md
0746.使用最小花费爬楼梯.md
0763.划分字母区间.md
0860.柠檬水找零.md
0968.监控二叉树.md
1005.K次取反后最大化的数组和.md
1035.不相交的线.md
1047.删除字符串中的所有相邻重复项.md
1049.最后一块石头的重量II.md
1143.最长公共子序列.md
O(n)的算法居然超时了,此时的n究竟是多大?.md
为了绝杀编辑距离,卡尔做了三步铺垫.md
二叉树中递归带着回溯.md
二叉树总结篇.md
二叉树理论基础.md
二叉树的理论基础.md
二叉树的统一迭代法.md
二叉树的迭代遍历.md
二叉树的递归遍历.md
关于时间复杂度,你不知道的都在这里!.md
剑指Offer05.替换空格.md
剑指Offer58-II.左旋转字符串.md
动态规划-股票问题总结篇.md
动态规划理论基础.md
双指针总结.md
哈希表总结.md
哈希表理论基础.md
回溯总结.md
回溯算法去重问题的另一种写法.md
回溯算法理论基础.md
字符串总结.md
数组总结篇.md
数组理论基础.md
栈与队列总结.md
栈与队列理论基础.md
根据身高重建队列(vector原理讲解).md
算法模板.md
背包总结篇.md
背包理论基础01背包-1.md
背包理论基础01背包-2.md
背包理论基础01背包-一维DP.md
背包理论基础01背包-二维DP.md
背包问题理论基础多重背包.md
背包问题理论基础完全背包.md
贪心算法总结篇.md
贪心算法理论基础.md
链表总结篇.md
链表理论基础.md
面试题02.07.链表相交.md
README.md
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
0037.解数独.md 11.35 KB
一键复制 编辑 原始数据 按行查看 历史

欢迎大家参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

如果对回溯法理论还不清楚的同学,可以先看这个视频视频来了!!带你学透回溯算法(理论篇)

37. 解数独

题目地址:https://leetcode-cn.com/problems/sudoku-solver/

编写一个程序,通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则: 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

解数独

一个数独。

解数独

答案被标成红色。

提示:

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

思路

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

怎么做二维递归呢?

大家已经跟着「代码随想录」刷过了如下回溯法题目,例如:77.组合(组合问题)131.分割回文串(分割问题)78.子集(子集问题)46.全排列(排列问题),以及51.N皇后(N皇后问题),其实这些题目都是一维递归。

如果以上这几道题目没有做过的话,不建议上来就做这道题哈!

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

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

因为这个树形结构太大了,我抽取一部分,如图所示:

37.解数独

回溯三部曲

  • 递归函数以及参数

递归函数的返回值需要是bool类型,为什么呢?

因为解数独找到一个符合的条件(就在树的叶子节点上)立刻就返回,相当于找从根节点到叶子节点一条唯一路径,所以需要使用bool返回值,这一点在回溯算法:N皇后问题中已经介绍过了,一样的道理。

代码如下:

bool backtracking(vector<vector<char>>& board)
  • 递归终止条件

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

不用终止条件会不会死循环?

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

那么有没有永远填不满的情况呢?

这个问题我在递归单层搜索逻辑里在来讲!

  • 递归单层搜索逻辑

37.解数独

在树形图中可以看出我们需要的是一个二维的递归(也就是两个for循环嵌套着递归)

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

代码如下:(详细看注释

bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] != '.') continue;
            for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                if (isValid(i, j, k, board)) {
                    board[i][j] = k;                // 放置k
                    if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                    board[i][j] = '.';              // 回溯,撤销k
                }
            }
            return false;                           // 9个数都试完了,都不行,那么就返回false
        }
    }
    return true; // 遍历完没有返回false,说明找到了合适棋盘位置了
}

注意这里return false的地方,这里放return false 是有讲究的

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

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

判断棋盘是否合法

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

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

代码如下:

bool isValid(int row, int col, char val, vector<vector<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;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == val ) {
                return false;
            }
        }
    }
    return true;
}

最后整体代码如下:

C++代码

class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] != '.') continue;
            for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                if (isValid(i, j, k, board)) {
                    board[i][j] = k;                // 放置k
                    if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                    board[i][j] = '.';              // 回溯,撤销k
                }
            }
            return false;                           // 9个数都试完了,都不行,那么就返回false
        }
    }
    return true; // 遍历完没有返回false,说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<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;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == val ) {
                return false;
            }
        }
    }
    return true;
}
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

总结

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

所以我在开篇就提到了二维递归,这也是我自创词汇,希望可以帮助大家理解解数独的搜索过程。

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

这样,解数独这么难的问题,也被我们攻克了

恭喜一路上坚持打卡的录友们,回溯算法已经接近尾声了,接下来就是要一波总结了

其他语言版本

Java:

class Solution {
    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;
    }
}

Python:

Go:


Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/open111/leetcode-master.git
git@gitee.com:open111/leetcode-master.git
open111
leetcode-master
leetcode-master
master

搜索帮助