0037.解数独

https://leetcode.cn/problems/sudoku-solver
方法一：回溯

时间复杂度 $O(9^{81})$，空间复杂度 $O(9^2)$。
func solveSudoku(board [][]byte) {
	row, col, box, t := [9][9]bool{}, [9][9]bool{}, [9][9]bool{}, [][2]int{}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			elem, k := int(board[i][j]-'1'), i/3*3+j/3
			if board[i][j] != '.' {
				row[i][elem], col[j][elem], box[k][elem] = true, true, true
			} else {
				t = append(t, [2]int{i, j})
			}
		}
	}
	var backtrack func(x int) bool

	backtrack = func(x int) bool {
		if x == len(t) {
			return true
		}
		i, j := t[x][0], t[x][1]
		for v := 1; v <= 9; v++ {
			if !row[i][v-1] && !col[j][v-1] && !box[i/3*3+j/3][v-1] {
				board[i][j] = byte('0' + v)
				row[i][v-1], col[j][v-1], box[i/3*3+j/3][v-1] = true, true, true
				if backtrack(x + 1) {
					return true
				}
				row[i][v-1], col[j][v-1], box[i/3*3+j/3][v-1] = false, false, false
			}
		}
		return false
	}
	backtrack(0)
}

func main() {
	v := [][]byte{
		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
		{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
	}
	solveSudoku(v)
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			fmt.Printf("%c ", v[i][j])
		}
		fmt.Println()
	}
}