📑 题目：37. 解数独

🚀 本题 LeetCode 传送门

题目大意

编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：

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

空白格用 ‘.’ 表示。

解题思路

• 给出一个数独谜题，要求解出这个数独
• 解题思路 DFS 暴力回溯枚举。数独要求每横行，每竖行，每九宫格内，1-9 的数字不能重复，每次放下一个数字的时候，在这 3 个地方都需要判断一次。
• 另外找到一组解以后就不需要再继续回溯了，直接返回即可。

代码

package leetcode
type position struct {
 x int
 y int
}
func solveSudoku(board [][]byte) {
 pos, find := []position{}, false
 for i := 0; i < len(board); i++ {
  for j := 0; j < len(board[0]); j++ {
   if board[i][j] == '.' {
    pos = append(pos, position{x: i, y: j})
   }
  }
 }
 putSudoku(&board, pos, 0, &find)
}
func putSudoku(board *[][]byte, pos []position, index int, succ *bool) {
 if *succ == true {
  return
 }
 if index == len(pos) {
  *succ = true
  return
 }
 for i := 1; i < 10; i++ {
  if checkSudoku(board, pos[index], i) && !*succ {
   (*board)[pos[index].x][pos[index].y] = byte(i) + '0'
   putSudoku(board, pos, index+1, succ)
   if *succ == true {
    return
   }
   (*board)[pos[index].x][pos[index].y] = '.'
  }
 }
}
func checkSudoku(board *[][]byte, pos position, val int) bool {
 // 判断横行是否有重复数字
 for i := 0; i < len((*board)[0]); i++ {
  if (*board)[pos.x][i] != '.' && int((*board)[pos.x][i]-'0') == val {
   return false
  }
 }
 // 判断竖行是否有重复数字
 for i := 0; i < len((*board)); i++ {
  if (*board)[i][pos.y] != '.' && int((*board)[i][pos.y]-'0') == val {
   return false
  }
 }
 // 判断九宫格是否有重复数字
 posx, posy := pos.x-pos.x%3, pos.y-pos.y%3
 for i := posx; i < posx+3; i++ {
  for j := posy; j < posy+3; j++ {
   if (*board)[i][j] != '.' && int((*board)[i][j]-'0') == val {
    return false
   }
  }
 }
 return true
}