DFS&BFS - 37. Sudoku Solver

37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

思路：

题目是让求解数组，就是每一行每一列每一个3*3的小方格不允许重复，做法和n皇后问题一样，就是使用dfs来枚举每一种填法，然后回溯。

代码：

go：

var col, row, box [][]bool

func initGrid(board [][]byte) {
    col = make([][]bool, 10)
    row = make([][]bool, 10)
    box = make([][]bool, 10)
    
    for i := range col {
        col[i] = make([]bool, 10)
        row[i] = make([]bool, 10)
        box[i] = make([]bool, 10)
    }
    
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            c := board[i][j]
            if c != '.' {
                col[j][c - '0'] = true
                row[i][c - '0'] = true
                box[j/3 + i/3*3][c - '0'] = true
            }
        }
    }
}

func dfs(board [][]byte, x int, y int) bool {
    if y == 9 {
        return true
    }
    
    nextX := (x + 1 ) % 9
    nextY := y
    if nextX == 0 {
        nextY = y + 1
    }
    
    if board[y][x] != '.' {
        return dfs(board, nextX, nextY)
    }
    
    // 枚举
    for num := byte(1); num <= 9; num++ {
        if !col[x][num] && !row[y][num] && !box[x/3 + y/3*3][num] {
            col[x][num] = true
            row[y][num] = true
            box[x/3 + y/3*3][num] = true
            board[y][x] = num + '0'
            if dfs(board, nextX, nextY) {
                return true
            }   
                
            col[x][num] = false
            row[y][num] = false
            box[x/3 + y/3*3][num] = false
            board[y][x] = '.'
        } 
    }
    
    return false
}

func solveSudoku(board [][]byte)  {
    initGrid(board)
    dfs(board, 0, 0)
}