[力扣_37] 解数独
这是第一道自己没看题解纯手撸出来的困难题~~~
题目入口:点击进入
相关算法:
- 深度优先搜索——时间复杂度O(9^9×9),空间复杂度O(9^9*9)[递归栈使用的空间]
思路和算法:
36题是这道题的前篇,如果做过八皇后和N皇后的话,对这道题应该就能有一个大概的思路,我们来看下题目要求:
可以看到,这是一道很经典的回溯问题,而这道问题的解就是一棵九叉树,为什么是九叉树呢?因为有九行,九列,每个格子又有九个数字的可能性,我们只需要采用上一题的思路,初始化三个检查数组即可。采用下【代码随想录】大佬的图:
DFS
递归首先需要确定的是参数的变化:
- 在这道题中,坐标会随之而变,给定的二维数组会随之而变,给定的检查数组会随之而变,我们可以整理如下:
- 数独数组、行、列、row检查数组、col检查数组、Samll检查数组。
再来看递归的出口:
- 当所有的格子全部迭代完,i=8、j=8,的时候,返回true,代表这个数独已经解完,所有格子都填上了对应的数字
再来看回溯条件:
-
什么情况需要回溯呢?当前格子所有数字(1到9)全部测试完,在三个检查数组中全为false的时候,就需要回到上一个状态,同时将上一个状态的三个检查表的状态恢复
- 也就是说,上一个状态填入的数字对应的三个检查表全部恢复成true,而上一个位置必须
回溯成'.'(这个很重要)
-
为什么需要回溯成'.'是因为再所有数字全部填写完并且没有可能的情况下,程序会不断回退,如不回溯 '.' 的话,在下一次再次进入这个格子的时候,就会将它当作已经填入的数字而不进行测试。
- 总之,在写回溯的时候,千万别抱有侥幸心理,觉得下一次的状态会覆盖这次的某一个状态而不进行还原!
再来看看程序的执行分支,什么是执行分支,也就是在进入递归的时候,根据当前参数的状态进行递归的选择。
-
当当前位置上是【数字】的情况下,我们通过判断边界进行递归,我们需要迭代所有格子,也就是需要遍历整个二维数组,则:
- 当 行 小于 boardSize 当列小于 boardColSize -1 时候,我们将 列坐标不断迭代
- i不变,j+1
- else if 当行小于 7 时,而列==8 时,代表此行的所有列都迭代完毕,就迭代下一行,
-
i+1, j 重新为0
- 当当前位置为【空白】的时候,我们循环九种可能【1-9】个数字不断去检查是否满足条件,如果满足,
则将当前位置标记上此数字,然后进行下一次递归,这里注意
- 由于当前位置已经是填入测试的数值,则在进行下一次递归的时候是从当前位置出发到下一个位置,不需要改变坐标。
- 然后判断此递归的返回值是否为ture,如果为true,则返回true到上一层,如果为false则进行回溯
整体程序确定好后,我们就可以写出DFS如下所示:
bool dfs(char **board,int boardSize,int boardColSize,int i,int j,bool **row , bool **col, bool ***SamllSudu){
if(i >=boardSize-1 && j >= boardColSize-1 && board[i][j]!='.'){
return true;
}
int SinRow=i/3;
int SinCol=j/3;
if(board[i][j]=='.'){//为空白时
for(int num=1;num<=9;num++){
if(row[i][num]==false || col[j][num]==false || SamllSudu[SinRow][SinCol][num]==false) continue;
row[i][num] = false;
col[j][num] = false;
SamllSudu[SinRow][SinCol][num] = false;
board[i][j]=num+'0';
if(dfs(board,boardSize,boardColSize,i,j,row,col,SamllSudu)){
return true;
}
else{
row[i][num]=true;
col[j][num]=true;
SamllSudu[SinRow][SinCol][num]=true;
board[i][j]='.';
}
}
}
else{//为已填充数字
if (i < boardSize&& j < boardColSize -1) {
return dfs(board, boardSize, boardColSize, i, j + 1, row, col, SamllSudu);
}
else if(i < boardSize-1){
return dfs(board, boardSize, boardColSize, i + 1, 0, row, col, SamllSudu);
}
}
return false;
}
而在DFS之前,我们需要采用36题的方法对三个数组进行初始化,唯一不同的是,这儿的Samll采用大佬的思路用了三位数组做Hash表
完整代码如下所示:
bool dfs(char **board,int boardSize,int boardColSize,int i,int j,bool **row , bool **col, bool ***SamllSudu){
if(i >=boardSize-1 && j >= boardColSize-1 && board[i][j]!='.'){
return true;
}
int SinRow=i/3;
int SinCol=j/3;
if(board[i][j]=='.'){//为空白时
for(int num=1;num<=9;num++){
if(row[i][num]==false || col[j][num]==false || SamllSudu[SinRow][SinCol][num]==false) continue;
row[i][num] = false;
col[j][num] = false;
SamllSudu[SinRow][SinCol][num] = false;
board[i][j]=num+'0';
if(dfs(board,boardSize,boardColSize,i,j,row,col,SamllSudu)){
return true;
}
else{
row[i][num]=true;
col[j][num]=true;
SamllSudu[SinRow][SinCol][num]=true;
board[i][j]='.';
}
}
}
else{//为已填充数字
if (i < boardSize&& j < boardColSize -1) {
return dfs(board, boardSize, boardColSize, i, j + 1, row, col, SamllSudu);
}
else if(i < boardSize-1){
return dfs(board, boardSize, boardColSize, i + 1, 0, row, col, SamllSudu);
}
}
return false;
}
void solveSudoku(char** board, int boardSize, int* boardColSize){
bool **row=(bool**)malloc(sizeof(bool*)*boardSize);
bool **col=(bool**)malloc(sizeof(bool*)*boardSize);
bool ***SamllSudu=(bool***)malloc(sizeof(bool**)*3);
for(int i=0;i < boardSize;i++){
row[i]=(bool*)malloc(sizeof(char)*((*boardColSize)+1));
col[i]=(bool*)malloc(sizeof(char)*((*boardColSize)+1));
for(int k=0;k<=(*boardColSize);k++){
row[i][k]=true;
col[i][k]=true;
}
}
for(int j=0; j < 3; j++){
SamllSudu[j]=(bool**)malloc(sizeof(bool*)*3);
for(int p=0;p<3;p++){
SamllSudu[j][p]=(bool*)malloc(sizeof(bool)*10);
for(int l=0;l<=9;l++){
SamllSudu[j][p][l]=true;
}
}
}
for(int n=0;n<boardSize;n++){
for(int m=0;m<(*boardColSize);m++){
if(board[n][m]!='.'){
int SinRow=n/3;
int SinCol=m/3;
row[n][board[n][m]-'0']=fals
col[m][board[n][m]-'0']=false;
SamllSudu[SinRow][SinCol][board[n][m]-'0']=false;
}
}
}
dfs(board,boardSize,(*boardColSize),0,0,row,col,SamllSudu);
return;
}