Sudoku Solver

Description

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character ‘.’. You may assume that there will be only one unique solution.

Solution

还是编程思维不行，在编程时按照解题思路在走。

我的答案： 查找空格，找出该位置可能的数字组合，填入，递归进入下一个空格。 这样虽然能解出答案。但是在查找可能的数字上耗费时间较多。

后面的Pretty Solution： 找到空格后，直接把依次把1-9填入，验证是否重复。反而耗时更少，代码也更简洁。

My solution

  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
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110

func solveSudoku(board [][]byte)  {
    setNumber(&board, 0)
}

func setNumber(board *[][]byte, index int) bool {
    row := int(index / 9)
    col := index % 9

    if index >= 81 {
        return true
    }

    canbe := getPossibleNumbers(*board, row, col)
    if len(canbe) == 0 {
        return false
    }

    reset := (*board)[row][col]
    ok := true
    for _, num := range canbe {
        (*board)[row][col] = num
        ok = setNumber(board, index + 1)
        if ok {
            break
        }
    }

    if !ok {
        (*board)[row][col] = reset
    }

    return ok
}

func getPossibleNumbers(board [][]byte, i, j int) []byte {
    num := board[i][j]
    if num != '.' {
        // skip this position
        return []byte{num}
    }

    canbe := map[byte]struct{}{
        '1': struct{}{},
        '2': struct{}{},
        '3': struct{}{},
        '4': struct{}{},
        '5': struct{}{},
        '6': struct{}{},
        '7': struct{}{},
        '8': struct{}{},
        '9': struct{}{},
    }

    // check row-i, remove number from 'canbe' which have been set to other postion
    for col := 0; col < 9; col++ {
        if col == j {
            continue
        }

        if removeFromPossibleNumber(&canbe, board[i][col]) == 0 {
            return []byte{}
        }
    }

    // check col-j, remove number from 'canbe' which have been set to other postion
    for row := 0; row < 9; row++ {
        if row == i {
            continue
        }
        if removeFromPossibleNumber(&canbe, board[row][j]) == 0 {
            return []byte{}
        }
    }

    // check the little sudoku block
    left := 3 * int(i / 3)
    top := 3 * int(j / 3)
    for l := 0; l < 3; l++ {
        for t := 0; t < 3; t++ {
            index_i := left + l
            index_j := top + t

            if index_i == i && index_j == j {
                continue
            }

            if removeFromPossibleNumber(&canbe, board[index_i][index_j]) == 0 {
                return []byte{}
            }
        }
    }

    var n byte
    var result []byte
    for n = '1'; n <= '9'; n++ {
        if _, ok := canbe[n]; ok {
            result = append(result, n)
        }
    }

    return result
}

func removeFromPossibleNumber(canbe *map[byte]struct{}, key byte) int {
    if _, ok := (*canbe)[key]; ok {
        delete(*canbe, key)
    }

    return len(*canbe)
}

Pretty solution

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

func solveSudoku(board [][]byte)  {
    setNumber(&board, 0)
}

func setNumber(board *[][]byte, index int) bool {
    row := int(index / 9)
    col := index % 9

    if index >= 81 {
        return true
    }

    if (*board)[row][col] == '.' {
        var c byte
        for c = '1'; c <= '9'; c++ {
            (*board)[row][col] = c
            if valid(board, row, col) && setNumber(board, index + 1) {
                return true
            }
            (*board)[row][col] = '.'
        }
        return false
    } else {
        return setNumber(board, index + 1)
    }
}

func valid(board *[][]byte, row, col int) bool {
    num := (*board)[row][col]

    // check row
    for i := 0; i < 9; i++ {
        if i == row {
            continue
        }
        if (*board)[i][col] == num {
            return false
        }
    }

    // check col
    for j := 0; j < 9; j++ {
        if j == col {
            continue
        }
        if (*board)[row][j] == num {
            return false
        }
    }

    // check the little sudoku block
    left := 3 * int(row / 3)
    top := 3 * int(col / 3)
    for i := left; i < left + 3; i++ {
        for j := top; j < top + 3; j++ {
            if i == row && j == col {
                continue
            }

            if (*board)[i][j] == num {
                return false
            }
        }
    }

    return true
}

Similar Problem

36. Valid-Sudoku