验证数独是否有效

验证数独是否有效

题目说明

判断一个9x9的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    sample
    上图是一个部分填充的有效的数独。
    数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

    解决方案

    本题主要是思想就是满足每行、每列和每个单元中不存在重复的数就可以,具体实现方式如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution:
    def isValidSudoku(self, board):
    """
    :type board: List[List[str]]
    :rtype: bool
    """
    if board is None:
    return False

    # 初始化rows、colunms和cells
    rows = [{},{},{},{},{},{},{},{},{}]
    columns = [{},{},{},{},{},{},{},{},{}]
    cells = [{},{},{},{},{},{},{},{},{}]

    for i in range(len(board)):
    for j in range(len(board[i])):
    # 计算cell的位置
    cell = 3 * (i // 3) + j // 3
    val = board[i][j]
    if val == '.':
    continue

    if val not in rows[i] and val not in columns[j] and val not in cells[cell]:
    rows[i][val] = 1
    columns[j][val] = 1
    cells[cell][val] = 1
    else:
    return False

    return True

说明: 如果您有更好的解决方案或者本人写的有什么问题,请多多指教!