 # DFS&BFS - 37. Sudoku Solver

1. 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`.

go：

``````var col, row, box [][]bool

func initGrid(board [][]byte) {
col = make([][]bool, 10)
row = make([][]bool, 10)
box = make([][]bool, 10)

for i := range col {
col[i] = make([]bool, 10)
row[i] = make([]bool, 10)
box[i] = make([]bool, 10)
}

for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
c := board[i][j]
if c != '.' {
col[j][c - '0'] = true
row[i][c - '0'] = true
box[j/3 + i/3*3][c - '0'] = true
}
}
}
}

func dfs(board [][]byte, x int, y int) bool {
if y == 9 {
return true
}

nextX := (x + 1 ) % 9
nextY := y
if nextX == 0 {
nextY = y + 1
}

if board[y][x] != '.' {
return dfs(board, nextX, nextY)
}

// 枚举
for num := byte(1); num <= 9; num++ {
if !col[x][num] && !row[y][num] && !box[x/3 + y/3*3][num] {
col[x][num] = true
row[y][num] = true
box[x/3 + y/3*3][num] = true
board[y][x] = num + '0'
if dfs(board, nextX, nextY) {
return true
}

col[x][num] = false
row[y][num] = false
box[x/3 + y/3*3][num] = false
board[y][x] = '.'
}
}

return false
}

func solveSudoku(board [][]byte)  {
initGrid(board)
dfs(board, 0, 0)
}
``````

Nothing just happens, it's all part of a plan.