Valid Sudoku - Leetcode Solution

Problem Statement:

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.

Solution:

The problem statement is quite clear, we are given a 9x9 Sudoku board with partially filled cells, and we need to determine whether the given Sudoku board is valid or not.

We can iterate over the given board and check the validity of each row, each column, and each 3x3 sub-box. We can use a set to keep track of the digits 1-9 for each row, column, and sub-box. If we encounter a repeated digit, we can return False.

The first step is to iterate over the board and validate each row:

def is_valid_sudoku(board) -> bool:
    for row in board:
        nums = set()
        for num in row:
            if num in nums:
                return False
            if num != ".":
                nums.add(num)
    return True

Next, we need to validate each column. We can use the zip() function to transpose the board so that we can iterate over each column:

def is_valid_sudoku(board) -> bool:
    for row in board:
        nums = set()
        for num in row:
            if num in nums:
                return False
            if num != ".":
                nums.add(num)

    for col in zip(*board):
        nums = set()
        for num in col:
            if num in nums:
                return False
            if num != ".":
                nums.add(num)
    return True

Finally, we need to validate each 3x3 sub-box. We can use nested loops to iterate over each sub-box. To determine the sub-box boundaries, we can use integer division to get the indices of the starting row and column of each sub-box:

def is_valid_sudoku(board) -> bool:
    for row in board:
        nums = set()
        for num in row:
            if num in nums:
                return False
            if num != ".":
                nums.add(num)

    for col in zip(*board):
        nums = set()
        for num in col:
            if num in nums:
                return False
            if num != ".":
                nums.add(num)

    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            nums = set()
            for k in range(3):
                for l in range(3):
                    num = board[i+k][j+l]
                    if num in nums:
                        return False
                    if num != ".":
                        nums.add(num)
    return True

Finally, we can combine all the above code snippets in a single function:

def is_valid_sudoku(board) -> bool:
    for row in board:
        nums = set()
        for num in row:
            if num in nums:
                return False
            if num != ".":
                nums.add(num)

    for col in zip(*board):
        nums = set()
        for num in col:
            if num in nums:
                return False
            if num != ".":
                nums.add(num)

    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            nums = set()
            for k in range(3):
                for l in range(3):
                    num = board[i+k][j+l]
                    if num in nums:
                        return False
                    if num != ".":
                        nums.add(num)
    return True

Note that we are checking all three conditions in a single pass, so the time complexity is O(81) = O(1). The space complexity is also constant, so the solution is quite efficient.

1