valid-sudoku.py

# Determine if a 9 x 9 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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
#
#
# 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.
#
#
#  
# Example 1:
#
#
# Input: board = 
# [["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: board = 
# [["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.
#
#
#  
# Constraints:
#
#
# 	board.length == 9
# 	board[i].length == 9
# 	board[i][j] is a digit 1-9 or '.'.
#
#


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def checkRows(board):
            for row in board:
                d = {}
                for num in row:
                    if num == ".":
                        continue
                    if num in d:
                        return False
                    d[num] = True
            return True
        def checkColumns(board):
            for i in range(9):
                d = {}
                for j in range(9):
                    num = board[j][i]
                    if num == ".":
                        continue
                    if num in d:
                        return False
                    d[num] = True
            return True
        def checkSquares(board):
            for i in range(0, 9, 3):
                for j in range(0, 9, 3):
                    d = {}
                    processElement(board[i][j], d)
                    processElement(board[i][j+1], d)
                    processElement(board[i][j+2], d)
                    processElement(board[i+1][j], d)
                    processElement(board[i+1][j+1], d)
                    processElement(board[i+1][j+2], d)
                    processElement(board[i+2][j], d)
                    processElement(board[i+2][j+1], d)
                    processElement(board[i+2][j+2], d)
                    for _, value in d.items():
                        if value > 1:
                            return False
            return True
        def processElement(e, d):
            if e == ".":
                return
            if e in d:
                d[e] += 1
                return
            d[e] = 1
        return checkRows(board) and checkColumns(board) and checkSquares(board)