探究解数独问题

探究解数独问题

本篇简介：

本篇文章基于leetcode的解数独问题展开讨论；通过对6有效数独的判断的基础下利用递归，结合剪枝回溯完成对本题解答。

一·解数独原题：

leetcode链接：7. 解数独 - 力扣（LeetCode）

在做这道题之前相比大家看到“困难”的flag就被吓到了；但是如何结合上一道也就是判断有效数独的灵活思路；其实仔细一想也不算困难。

因此做解数独之前我们先把如何用巧方法判断数独是否有效：

下面就是leetcode的6题了：

链接：6. 有效的数独 - 力扣（LeetCode）

关键就是三个条件：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 x 宫内只能出现一次。

下面我们画图解释一下：

这里我们当遍历这个二维数组某个位置，则需要根据这三个条件判断是否合适；因此这里创建三个bool数组：来分别帮我们判断某行是否存在某个数；某列是否存在某个数；某个*的方格是否存在某个数。

代码语言：javascript代码运行次数：0运行复制

   bool row[9][10]={false};//某行是否存在1-9

    bool col[9][10]={false};//某列是否存在1-9

    bool grid[][][10]={false};//某个小方块是否存在1-9

这里第二个下标也可以是0-9；只需要调整一下映射位置；这里设置为10方便直接映射。

也许会说这里涉及的很巧妙？

这里的题确实类似之前做过的皇后的题型，都是自己设计bool数组完成对条件是否满足的判断。

这里只不过多了个对是否小方格内出现多了一个三维的bool类型check数组（这里也不难发现下标对应除就是对应所在小方格的下标了）

下面就可以解答了：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
//思路：确立好检查行列以及小方块的三个bool数组；遍历它去判断即可.
   //检查是否出现不符合的三种情况：
    bool row[9][10]={false};//某行是否存在1-9；
    bool col[9][10]={false};//某列是否存在1-9
    bool grid[][][10]={false};//某个小方块是否存在1-9
    bool isValidSudoku(vector<vector<char>>& b) {
     for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
          if(b[i][j]=='.') continue;
          int num=b[i][j]-'0';
          if(row[i][num]||col[j][num]||grid[i/][j/][num]) return false;
          row[i][num]=col[j][num]=grid[i/][j/][num]=true;
        }   
     }
 return true;
    }
};

由判断有效数独的小总结：这里个人认为关键还是判断三个条件，因此巧妙就在于设计的那三个check数组了 。

二·解数独的思路：

此时我们有了上面所述判断是否符合数独的基础；这道题便用到了，简单来说；再结合上我们做过的决策树系列的题的解法思路：画树->分析如何递归->确立好函数的返回值参数类型->处理好递归出口，回溯，剪枝等。 下面我们就就题分析一下：

目标 ：

不过首先它可能是有已经填好的数字的故我们需要给那三个check 的bool数组初始化一下，以防之后填充出现错误：

代码语言：javascript代码运行次数：0运行复制

for(int i=0;i<9;i++){//把bool数组初始化；也就是已经被填充的给它在bool数组标记上
            for(int j=0;j<9;j++){
                if(board[i][j]!='.')
                 row[i][board[i][j]-'0']=col[j][board[i][j]-'0']=grid[i/][j/][board[i][j]-'0']=true;
            }
        }

但是这里如果完整的画出决策树过于麻烦，就草图一下吧：

这里个人觉得：除了上面所说的三个check数组外，其次比较注意的就是这三个返回值的位置的设计了；把握好这点，其次就是处理好的剪枝和回溯的细节问题；这道题问题也就不大了。

三·代码解答： 代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
   bool row[9][10]={false};//某行是否存在1-9；
    bool col[9][10]={false};//某列是否存在1-9
    bool grid[][][10]={false};//某个小方块是否存在1-9

    void solveSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++){//把bool数组初始化；也就是已经被填充的给它在bool数组标记上
            for(int j=0;j<9;j++){
                if(board[i][j]!='.')
                 row[i][board[i][j]-'0']=col[j][board[i][j]-'0']=grid[i/][j/][board[i][j]-'0']=true;
            }
        }
        dfs( board);
    }
    //这里bool数组需要返回值为方便我们知道最后的情况是否是合适的：要么都填满要么填到某个位置发现1-9都不合适了此时对应返回true和false
    bool dfs(vector<vector<char>>& board){
       for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            //到是'.'开始填充
            if(board[i][j]=='.'){
                for(int num=1;num<=9;num++){
                 if(!row[i][num]&&!col[j][num]&&!grid[i/][j/][num]){
                    board[i][j]=num+'0';
                    row[i][num]=col[j][num]=grid[i/][j/][num]=true;
                    //剪枝：
                    if(dfs(board)) return true;//这里对应的是如果dfs返回的true那么直接一层层往上传
                    else {
                        //当前位置填充这个数不合适恢复现场，重新从1-9选择：
                        board[i][j]='.';
                         row[i][num]=col[j][num]=grid[i/][j/][num]=false;
                    }

                 }
                }
                return false;//到最后无法选择1-9中合适的数填充
            }
        }
       }
       return true;//假设完全填完后，没有'.'则此时就应该一层层向上告诉完成了true
    }
};

个人小结：

对于做了很多决策树类型的题；可以发现好多题目都会用到了bool类型的check数组完成对要求检查，以及在数组里面标记，为了后面像剪枝回溯等操作的进行，这些关键还是要处理好。 一般步骤：读懂题意->画出决策树->分析如何递归，怎么递归到下一层（这些条件方便些dfs函数体，以及剪枝，回溯的处理）->直接到最后一次递归的情况分析处递归出口->涉及好函数体以及需要参数，返回类型等。 欢迎大家阅读，如有不足之处欢迎留言指出，感谢支持！！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-17，如有侵权请联系 cloudcommunity@tencent 删除前往查看数组决策树递归函数设计