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