LeetCode37-解数独，DFS（Golang）

LeetCode37-解数独

题意：

• 给定一个数独题目，要求解出该数独。
• 数独规则：
  • 每行、每列、每个九宫格都只包含不重复的数字1-9

题解：

• 解数独，是DFS的典型题目，一看到解数独，就要想到DFS
• 具体做法：
  • 对于每一个未填入数字的格子，枚举1-9，只有当该数字符合当前对于不重复这一条件的限制的时候，才将其填入
  • 如何判断不重复呢？可以用三个vis数组来维护当前状态下，数字的访问情况。
    • 用visr[i]，来表示当前状态下第 i 行的数字使用情况
    • 用visc[j]，来表示当前状态下第 j 列的数字使用情况
    • 用visg[k]，来表示当前状态下第 k 个九宫格的数字使用情况
      • 其中，经稍微推敲可的，k=i/3*3+j

代码（Golang）：

func solveSudoku(board [][]byte)  {    //三个vis数组用于维护数字占用情况    visr,visc,visg:=make([][]bool,9),make([][]bool,9),make([][]bool,9)    //go语言初始化每个数组    for i:=0;i<9;i++{ visr[i],visg[i],visc[i]=make([]bool,9),make([]bool,9),make([]bool,9)    }    //对一开始的数字占用情况进行记录    for i:=0;i<9;i++{ for j:=0;j<9;j++{     if board[i][j]!='.'{  tmp:=int(board[i][j])-49  visr[i][tmp]=true  visc[j][tmp]=true  visg[i/3*3+j/3][tmp]=true     } }    }    //dfs函数定义    var dfs func(i,j int)bool    dfs=func(i,j int)bool{ //当i==9时，表示的是i==8&&j==8已经得到正确搜索，故直接返回 if i==9{     return true } //当前数字未填写，则开始枚举 if board[i][j]=='.'{     for dig:=0;dig<9;dig++{//枚举  if !visc[j][dig] && !visr[i][dig] && !visg[i/3*3+j/3][dig]{      visc[j][dig],visr[i][dig],visg[i/3*3+j/3][dig]=true,true,true      board[i][j]=byte(dig+49)      if j==8 {   tag:=dfs(i+1,0)   if tag{return true   }      }else{   tag:=dfs(i,j+1)   if tag{return true   }      }   //搜索后且为return，则说明该枚举行不通，要恢复搜索前的情况      board[i][j]='.'      visc[j][dig],visr[i][dig],visg[i/3*3+j/3][dig]=false,false,false  }     } }else{     if j==8{  tag:=dfs(i+1,0)  if tag{      return true  }     }else {  tag:=dfs(i,j+1)  if tag{      return true  }     } } return false    }    //调用函数，轻松过题    dfs(0,0)}