探究解数独问题
本篇简介：
本篇文章基于leetcode的解数独问题展开讨论；通过对36有效数独的判断的基础下利用递归，结合剪枝回溯完成对本题解答。
一·解数独原题：
leetcode链接：37. 解数独 - 力扣（LeetCode）
在做这道题之前相比大家看到“困难”的flag就被吓到了；但是如何结合上一道也就是判断有效数独的灵活思路；其实仔细一想也不算困难。
因此做解数独之前我们先把如何用巧方法判断数独是否有效：
下面就是leetcode的36题了：
关键就是三个条件：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
下面我们画图解释一下：
这里我们当遍历这个二维数组某个位置，则需要根据这三个条件判断是否合适；因此这里创建三个bool数组：来分别帮我们判断某行是否存在某个数；某列是否存在某个数；某个3*3的方格是否存在某个数。
bool row[9][10]={false};//某行是否存在1-9
bool col[9][10]={false};//某列是否存在1-9
bool grid[3][3][10]={false};//某个小方块是否存在1-9这里第二个下标也可以是0-9；只需要调整一下映射位置；这里设置为10方便直接映射。
也许会说这里涉及的很巧妙？
这里的题确实类似之前做过的N皇后的题型，都是自己设计bool数组完成对条件是否满足的判断。
这里只不过多了个对是否小方格内出现多了一个三维的bool类型check数组（这里也不难发现下标对应除3就是对应所在小方格的下标了）
下面就可以解答了：
class Solution {
public:
//思路：确立好检查行列以及小方块的三个bool数组；遍历它去判断即可.
//检查是否出现不符合的三种情况：
bool row[9][10]={false};//某行是否存在1-9；
bool col[9][10]={false};//某列是否存在1-9
bool grid[3][3][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/3][j/3][num]) return false;
row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
}
}
return true;
}
};由判断有效数独的小总结：这里个人认为关键还是判断三个条件，因此巧妙就在于设计的那三个check数组了 。
二·解数独的思路：
此时我们有了上面所述判断是否符合数独的基础；这道题便用到了，简单来说；再结合上我们做过的决策树系列的题的解法思路：画树->分析如何递归->确立好函数的返回值参数类型->处理好递归出口，回溯，剪枝等。 下面我们就就题分析一下：
目标 ：
不过首先它可能是有已经填好的数字的故我们需要给那三个check 的bool数组初始化一下，以防之后填充出现错误：
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/3][j/3][board[i][j]-'0']=true;
}
}但是这里如果完整的画出决策树过于麻烦，就草图一下吧：
这里个人觉得：除了上面所说的三个check数组外，其次比较注意的就是这三个返回值的位置的设计了；把握好这点，其次就是处理好的剪枝和回溯的细节问题；这道题问题也就不大了。
三·代码解答：
class Solution {
public:
bool row[9][10]={false};//某行是否存在1-9；
bool col[9][10]={false};//某列是否存在1-9
bool grid[3][3][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/3][j/3][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/3][j/3][num]){
board[i][j]=num+'0';
row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
//剪枝：
if(dfs(board)) return true;//这里对应的是如果dfs返回的true那么直接一层层往上传
else {
//当前位置填充这个数不合适恢复现场，重新从1-9选择：
board[i][j]='.';
row[i][num]=col[j][num]=grid[i/3][j/3][num]=false;
}
}
}
return false;//到最后无法选择1-9中合适的数填充
}
}
}
return true;//假设完全填完后，没有'.'则此时就应该一层层向上告诉完成了true
}
};个人小结：
对于做了很多决策树类型的题；可以发现好多题目都会用到了bool类型的check数组完成对要求检查，以及在数组里面标记，为了后面像剪枝回溯等操作的进行，这些关键还是要处理好。 一般步骤：读懂题意->画出决策树->分析如何递归，怎么递归到下一层（这些条件方便些dfs函数体，以及剪枝，回溯的处理）->直接到最后一次递归的情况分析处递归出口->涉及好函数体以及需要参数，返回类型等。 欢迎大家阅读，如有不足之处欢迎留言指出，感谢支持！！！
腾讯云开发者
