menu

[LeetCode] 036. Valid Sodoku

Problem (Medium)

036. Valid Sodoku

Determine if a 9x9 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 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.

Approach 1: (My Solution)

Idea

Check the three conditions one by one:

  • each row;
  • each column;
  • each 3x3 block.

Solution

class Solution1:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # For each row
        for line in board:
            pool = []
            for c in line:
                if c == '.':
                    continue
                elif not c in pool:
                    pool.append(c)
                else:
                    return False
        # For each column
        for col in range(9):
            pool = []
            for row in range(9):
                tmp = board[row][col]
                if tmp == '.':
                    continue
                elif not tmp in pool:
                    pool.append(tmp)
                else:
                    return False
        # For each 3x3 block
        for c_i in range(3): # 
            for c_j in range(3):
                pool = []
                for row in range(3):
                    for col in range(3):
                        tmp = board[c_i*3+row][c_j*3+col]
                        if tmp == '.':
                            continue
                        elif not tmp in pool:
                            pool.append(tmp)
                        else:
                            return False
        return True

Complexity

  • Time: $O()$?
  • Space: $O()$?

Approach 2: 3 Cases Check in One Loop

Idea

pythonic - check 3 cases in one loop.

Solution

class Solution2:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        pool = [[('row', i, c), ('col', j, c), ('block',i//3, j//3, c)]
                for i, row in enumerate(board) 
                for j, c in enumerate(row) if c != '.']
        pool = sum(pool, [])
        return len(pool) == len(set(pool))



KF

Comments