Medium

Valid Sudoku

Description

Check whether a 9 x 9 board obeys Sudoku's uniqueness rules. Each digit 1 through 9 may appear once per row, column, and 3 x 3 box; dots are empty cells. You are checking the filled cells, not solving the puzzle.

Solution

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    columns = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for row in range(9):
        for col in range(9):
            digit = board[row][col]
            if digit == ".":
                continue
            box = (row // 3) * 3 + col // 3
            if digit in rows[row] or digit in columns[col] or digit in boxes[box]:
                return False
            rows[row].add(digit)
            columns[col].add(digit)
            boxes[box].add(digit)
    return True

Examples

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

No filled digit repeats in a row, column, or box.

Example 2

Input
[[["5","5",".",".","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

The first row contains two 5s.

Example 3

Input
[[["1",".",".",".",".",".",".",".","."],[".","1",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]]
Output
false

The two 1s share a 3 x 3 box, even though their rows and columns differ.

Approach

Track seen digits separately for each row, column, and box. For a filled cell, compute its box index from integer division by three. Reject any repeated digit; otherwise insert it into all three sets.

Time & space

O(1) time and O(1) auxiliary space for the fixed 81-cell board.