37. 解数独

题目描述

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：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"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

解法一：回溯

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


func solveSudoku(board [][]byte) {
    var rowRecord, colRecord [9][10]bool
    var blockRecord [3][3][10]bool
    var spaces [][2]int

    for rowIdx, row := range board {
        for colIdx, ch := range row {
            if ch == '.' {
                spaces = append(spaces, [2]int{rowIdx, colIdx})
            } else {
                num := ch - '0'
                rowRecord[rowIdx][num] = true
                colRecord[colIdx][num] = true
                blockRecord[rowIdx/3][colIdx/3][num] = true
            }
        }
    }
    var dfs func(pos int) bool
    dfs = func(pos int) bool {
        if pos == len(spaces) {
            return true
        }
        rowIdx, colIdx := spaces[pos][0], spaces[pos][1]
        for digit := 1; digit <= 9; digit++ {
            if !rowRecord[rowIdx][digit] && !colRecord[colIdx][digit] &&
                !blockRecord[rowIdx/3][colIdx/3][digit] {
                rowRecord[rowIdx][digit] = true
                colRecord[colIdx][digit] = true
                blockRecord[rowIdx/3][colIdx/3][digit] = true
                board[rowIdx][colIdx] = byte('0' + digit)
                if dfs(pos + 1) {
                    return true
                }
                rowRecord[rowIdx][digit] = false
                colRecord[colIdx][digit] = false
                blockRecord[rowIdx/3][colIdx/3][digit] = false
            }
        }
        return false
    }
    dfs(0)
    return
}