<filename>36.valid-sudoku.py
#
# @lc app=leetcode id=36 lang=python
#
# [36] Valid Sudoku
#
# https://leetcode.com/problems/valid-sudoku/description/
#
# algorithms
# Medium (41.93%)
# Total Accepted:    216.5K
# Total Submissions: 516.5K
# 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 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
#
#
# 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.
#
#
#
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row = len(board)
        col = len(board[0])
        for i in range(row):
            row_elem = []
            col_elem = []
            sub_mat_elem = []
            for j in range(col):
                if board[i][j] != '.':
                    if board[i][j] not in row_elem:
                        row_elem.append(board[i][j])
                    else:
                        return False
                if board[j][i] != '.':
                    if board[j][i] not in col_elem:
                        col_elem.append(board[j][i])
                    else:
                        return False
                mat_row = 3*(i/3)
                mat_col = 3*(i%3)
                if board[mat_row+j/3][mat_col+j%3] != '.':
                    if board[mat_row+j/3][mat_col+j%3] not in sub_mat_elem:
                        sub_mat_elem.append(board[mat_row+j/3][mat_col+j%3])
                    else:
                        return False
        return True




<filename>36.valid-sudoku.py
#
# @lc app=leetcode id=36 lang=python
#
# [36] Valid Sudoku
#
# https://leetcode.com/problems/valid-sudoku/description/
#
# algorithms
# Medium (41.93%)
# Total Accepted:    216.5K
# Total Submissions: 516.5K
# 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 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
#
#
# 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.
#
#
#
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row = len(board)
        col = len(board[0])
        for i in range(row):
            row_elem = []
            col_elem = []
            sub_mat_elem = []
            for j in range(col):
                if board[i][j] != '.':
                    if board[i][j] not in row_elem:
                        row_elem.append(board[i][j])
                    else:
                        return False
                if board[j][i] != '.':
                    if board[j][i] not in col_elem:
                        col_elem.append(board[j][i])
                    else:
                        return False
                mat_row = 3*(i/3)
                mat_col = 3*(i%3)
                if board[mat_row+j/3][mat_col+j%3] != '.':
                    if board[mat_row+j/3][mat_col+j%3] not in sub_mat_elem:
                        sub_mat_elem.append(board[mat_row+j/3][mat_col+j%3])
                    else:
                        return False
        return True




# # @lc app=leetcode id=36 lang=python # # [36] Valid Sudoku # # https://leetcode.com/problems/valid-sudoku/description/ # # algorithms # Medium (41.93%) # Total Accepted:    216.5K # Total Submissions: 516.5K # 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 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 # # # 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. # # # :type board: List[List[str]]         :rtype: bool