Leetcode 36. Valid Sudoku

Determine if a 9 x 9 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 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 3×3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

There are some magic solutions on Leetcode, but I chose the dumb one which is checking all rules one by one.

I think the only part tricky is checking column, zip(*board).

zip is a built-in function that can go through multiple iterable items in a for loop.

*board will unpack board.

For example, if board = [[1,2,3], [4,5,6], [7,8,9]], then *board = [1,2,3] [4,5,6] [7,8,9].

When use with zip, then we can easily get column elements.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        return self.is_column_valid(board) and self.is_row_valid(board) and self.is_subbox_valid(board)

    def is_column_valid(self, board: List[List[str]]) -> bool:
        for column in zip(*board):
            if not self.is_valid(column):
                return False
        return True

    def is_row_valid(self, board: List[List[str]]) -> bool:
        for row in board:
            if not self.is_valid(row):
                return False
        return True

    def is_subbox_valid(self, board: List[List[str]]) -> bool:
        for row_start in range(0, 9, 3):
            for column_start in range(0, 9, 3):
                elements = [board[x][y] for x in range(row_start, row_start+3) for y in range(column_start, column_start+3)]
                if not self.is_valid(elements):
                    return False
        return True

    def is_valid(self, elements: List[str]) -> bool:
        valid_elements = list(filter(lambda x : x != ".", elements))

        return len(valid_elements) == len(set(valid_elements))