[Day43]-[回溯]- 解数独

输入：board = [["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"]]输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

func TestSolveSudoku(t *testing.T) {	var m = 9                                        // 9x9 的格子	var board [][]byte                               // 数独	var isValid func(row, col int, target byte) bool // 是否合法	var traceback func(row, col int) bool            // 回溯
	isValid = func(row, col int, target byte) bool {		for i := 0; i < m; i++ {			if board[row][i] == target { // 同一行不能重复				return false			}			if board[i][col] == target { // 同一列不能重复				return false			}			if board[row/3*3+i/3][col/3*3+i%3] == target { //3x3区域不能重复				return false			}		}		return true	}
	// 初始化棋盘	func() {		board = make([][]byte, m)		for i := 0; i < m; i++ {			board[i] = make([]byte, m)		}		for i := 0; i < m; i++ {			for j := 0; j < m; j++ {				board[i][j] = '.'			}		}	}()
	traceback = func(row, col int) bool {		if col == m {			return traceback(row+1, 0)
		}		if row == m {			return true		}		if board[row][col] != '.' {			return traceback(row, col+1)		}
		for i := '1'; i <= '9'; i++ {			if !isValid(row, col, byte(i)) {				continue			}			board[row][col] = byte(i)			if traceback(row, col+1) {				return true			}			board[row][col] = '.'		}		return false	}	traceback(0, 0)	for i := 0; i < m; i++ {		fmt.Println()		for j := 0; j < m; j++ {			fmt.Print(string(board[i][j]))		}	}}