Valid Sudoku

Description

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

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. 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

Example 2:

Input:
[
  ["8","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: false

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8.
Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character ‘.’. The given board size is always 9x9.

判断数独板是否有效。

注：

一个数组板可以是有效但是无解的。

Solution

根据题意只需要判断数独板中给出的数字在行列和3x3格子中是否有重复即可。而不需要判断是否可以解。

func isValidSudoku(board [][]byte) bool {
    // 用于标记第x列已使用的数字
    colUsed := [9][9]bool{}
    // 用于标记3x3小方格已使用的数字
    subBoxUsed := [3][3][9]bool{}

    for row := 0; row < 9; row++ {
        // 用于标记当前行已使用的数字
        rowUsed := [9]bool{}

        for col := 0; col < 9; col++ {
            b := board[row][col]
            if b == '.' {
                continue
            }

            num := b - '0' - 1

            // 检查数字是否已使用
            if rowUsed[num] || colUsed[col][num] || subBoxUsed[row / 3][col / 3][num] {
                return false
            }

            // 标记为已使用
            rowUsed[num] = true
            colUsed[col][num] = true
            subBoxUsed[row / 3][col / 3][num] = true
        }
    }

    return true
}

Similar Problem

37. Sudoku-Solver