[力扣_37] 解数独

这是第一道自己没看题解纯手撸出来的困难题~~~

题目入口:点击进入

相关算法:

  • 深度优先搜索——时间复杂度O(9^9×9),空间复杂度O(9^9*9)[递归栈使用的空间]

思路和算法:

36题是这道题的前篇,如果做过八皇后和N皇后的话,对这道题应该就能有一个大概的思路,我们来看下题目要求:

img

可以看到,这是一道很经典的回溯问题,而这道问题的解就是一棵九叉树,为什么是九叉树呢?因为有九行,九列,每个格子又有九个数字的可能性,我们只需要采用上一题的思路,初始化三个检查数组即可。采用下【代码随想录】大佬的图:

img

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;
}

本文链接:

https://nullcode.fun/84.html
1 + 7 =
快来做第一个评论的人吧~