# @lc app=leetcode id=36 lang=python3
#
# [36] Valid Sudoku
#
# https://leetcode.com/problems/valid-sudoku/description/
#
# algorithms
# Medium (50.84%)
# Likes:    2471
# Dislikes: 553
# Total Accepted:    466.4K
# Total Submissions: 916.6K
# Testcase Example:  '[["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"]]'
#
# 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 or '.'.
#
#
#
#
#

# @lc tags=hash-table

# @lc imports=start
from imports import *

# @lc imports=end

# @lc idea=start
#
# 判断是否是合法的数独。
# 分组判断即可，使用三个长度为9*9的数组分别存储行列块的内容。
# 块索引为 b[i // 3 * 3 + j // 3]。
#
# @lc idea=end

# @lc group=

# @lc rank=


# @lc code=start
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        self.board = board

        self.r = [[False for _ in range(10)] for _ in range(9)]
        self.c = [[False for _ in range(10)] for _ in range(9)]
        self.b = [[False for _ in range(10)] for _ in range(9)]
        for i in range(9):
            for j in range(9):
                if self.board[i][j] == '.':
                    self.board[i][j] = 0
                else:
                    self.board[i][j] = ord(self.board[i][j]) - 48
                    if self.r[i][self.board[i][j]] or self.c[j][
                            self.board[i][j]] or self.b[i // 3 * 3 + j //
                                                        3][self.board[i][j]]:
                        return False
                    self.r[i][self.board[i][j]] = True
                    self.c[j][self.board[i][j]] = True
                    self.b[i // 3 * 3 + j // 3][self.board[i][j]] = True
        return True

        pass


# @lc code=end

# @lc main=start
if __name__ == '__main__':
    print('Example 1:')
    print('Input : ')
    print(
        '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"]]'
    )
    print('Output :')
    print(
        str(Solution().isValidSudoku(
            [["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"]])))
    print('Exception :')
    print('true')
    print()

    print('Example 2:')
    print('Input : ')
    print(
        '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"]]'
    )
    print('Output :')
    print(
        str(Solution().isValidSudoku(
            [["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"]])))
    print('Exception :')
    print('false')
    print()

    pass
# @lc main=end
# @lc app=leetcode id=36 lang=python3
#
# [36] Valid Sudoku
#
# https://leetcode.com/problems/valid-sudoku/description/
#
# algorithms
# Medium (50.84%)
# Likes:    2471
# Dislikes: 553
# Total Accepted:    466.4K
# Total Submissions: 916.6K
# Testcase Example:  '[["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"]]'
#
# 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 or '.'.
#
#
#
#
#

# @lc tags=hash-table

# @lc imports=start
from imports import *

# @lc imports=end

# @lc idea=start
#
# 判断是否是合法的数独。
# 分组判断即可，使用三个长度为9*9的数组分别存储行列块的内容。
# 块索引为 b[i // 3 * 3 + j // 3]。
#
# @lc idea=end

# @lc group=

# @lc rank=


# @lc code=start
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        self.board = board

        self.r = [[False for _ in range(10)] for _ in range(9)]
        self.c = [[False for _ in range(10)] for _ in range(9)]
        self.b = [[False for _ in range(10)] for _ in range(9)]
        for i in range(9):
            for j in range(9):
                if self.board[i][j] == '.':
                    self.board[i][j] = 0
                else:
                    self.board[i][j] = ord(self.board[i][j]) - 48
                    if self.r[i][self.board[i][j]] or self.c[j][
                            self.board[i][j]] or self.b[i // 3 * 3 + j //
                                                        3][self.board[i][j]]:
                        return False
                    self.r[i][self.board[i][j]] = True
                    self.c[j][self.board[i][j]] = True
                    self.b[i // 3 * 3 + j // 3][self.board[i][j]] = True
        return True

        pass


# @lc code=end

# @lc main=start
if __name__ == '__main__':
    print('Example 1:')
    print('Input : ')
    print(
        '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"]]'
    )
    print('Output :')
    print(
        str(Solution().isValidSudoku(
            [["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"]])))
    print('Exception :')
    print('true')
    print()

    print('Example 2:')
    print('Input : ')
    print(
        '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"]]'
    )
    print('Output :')
    print(
        str(Solution().isValidSudoku(
            [["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"]])))
    print('Exception :')
    print('false')
    print()

    pass
# @lc main=end
# @lc app=leetcode id=36 lang=python3 # # [36] Valid Sudoku # # https://leetcode.com/problems/valid-sudoku/description/ # # algorithms # Medium (50.84%) # Likes:    2471 # Dislikes: 553 # Total Accepted:    466.4K # Total Submissions: 916.6K # Testcase Example:  '[["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"]]' # # 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 or '.'. # # # # # # @lc tags=hash-table # @lc imports=start # @lc imports=end # @lc idea=start # # 判断是否是合法的数独。 # 分组判断即可，使用三个长度为9*9的数组分别存储行列块的内容。 # 块索引为 b[i // 3 * 3 + j // 3]。 # # @lc idea=end # @lc group= # @lc rank= # @lc code=start # @lc code=end # @lc main=start # @lc main=end