文章 217
评论 6
浏览 143930
DFS&BFS - 37. Sudoku Solver

DFS&BFS - 37. Sudoku Solver

  1. 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 '.'.

null
A sudoku puzzle...

null
...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)
}


标题:DFS&BFS - 37. Sudoku Solver
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2020/02/11/1581416179432.html

Nothing just happens, it's all part of a plan.

取消