数独

[编程题]数独

热度指数：11604 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请编写一个程序，给数独中的剩余的空格填写上数字

空格用字符'.'表示

假设给定的数独只有唯一的解法

这盘数独的解法是：

红色表示填上的解

示例1

输入

[[.,.,9,7,4,8,.,.,.],[7,.,.,.,.,.,.,.,.],[.,2,.,1,.,9,.,.,.],[.,.,7,.,.,.,2,4,.],[.,6,4,.,1,.,5,9,.],[.,9,8,.,.,.,3,.,.],[.,.,.,8,.,3,.,2,.],[.,.,.,.,.,.,.,.,6],[.,.,.,2,7,5,9,.,.]]

输出

[[5,1,9,7,4,8,6,3,2],[7,8,3,6,5,2,4,1,9],[4,2,6,1,3,9,8,7,5],[3,5,7,9,8,6,2,4,1],[2,6,4,3,1,7,5,9,8],[1,9,8,5,2,4,3,6,7],[9,7,5,8,6,3,1,2,4],[8,3,2,4,9,1,7,5,6],[6,4,1,2,7,5,9,8,3]]

算法知识视频讲解

bigkai

var row, col int
var rows, cols, tmp [][]bool
func solveSudoku( board [][]byte ) {
    if row = len(board); row == 0 {
        return
    }
    if col = len(board[0]); col == 0 {
        return
    }
    rows, cols, tmp = make([][]bool, row), make([][]bool, row), make([][]bool, row)
    for i := 0; i < row; i++ {
        rows[i] = make([]bool, col)
        cols[i] = make([]bool, col)
        tmp[i] = make([]bool, col)
    }

    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if (board[i][j] != '.') {
                num := int(board[i][j] - '1')
                rows[i][num] = true
                cols[j][num] = true
                tmp[i / 3 * 3 + j / 3][num] = true
            }
        }
    }

    dfs(board, 0, 0)
}

func dfs(board [][]byte, i, j int) bool {
    for board[i][j] != '.' {
        j++
        if j >= col {
            i++
            j = 0
        }
        if i >= row {
            return true
        }
    }

    for k := 0; k < row; k++ {
        idx := i / 3 * 3 + j / 3
        if !rows[i][k] && !cols[j][k] && !tmp[idx][k] {
            board[i][j] = byte(k + '1')
            rows[i][k], cols[j][k], tmp[idx][k] = true, true, true
            if dfs(board, i, j) {
                return true
            }
            board[i][j] = '.'
            rows[i][k], cols[j][k], tmp[idx][k] = false, false, false
        }
    }

    return false
}

发表于 2021-08-14 14:14:30 回复(0)