0037. Sudoku Solver

# 37. Sudoku Solver#

## 题目 #

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

Empty cells are indicated by the character `'.'`.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

• The given board contain only digits `1-9` and the character `'.'`.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always `9x9`.

## 题目大意 #

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
}

``````

Sep 6, 2020