Array - 36. Valid Sudoku

ppxai

发布于 2020-09-23 17:46:17

3750

发布于 2020-09-23 17:46:17

36.Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

思路：

题目意思是给定一个数独，验证数独矩阵是否合法，就是每一行不允许有数字重复，每一列不允许有数字重复，每个3*3的小方阵也不允许有数字重复，采用三个二维矩阵来记录对应行，列和小方阵的情况即可。 这里题目意思有点模糊，如果保证了每行每列每个小方阵不允许全为空，case又报错。

代码：

go：

func isValidSudoku(board [][]byte) bool {
    var col, row, subBox [10][10]bool
    
    for i := range board {
        for j, c := range board[i] {
            if c == '.' {
                continue
            }
            if col[i][c - '0'] || row[j][c - '0'] || subBox[i/3 + j/3*3][c - '0'] {
                return false
            }
            
            col[i][c - '0'] = true
            row[j][c - '0'] = true
            subBox[i/3 + j/3*3][c - '0'] = true
        }
    }
    
    return true
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020年05月17日，如有侵权请联系 cloudcommunity@tencent.com 删除

digits