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 TrueExamples
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.