Valid Sudoku

The problem

Given a 9×9 Sudoku board (filled cells are digit strings, empty cells are '.'), decide whether the current state could extend to a valid solution. That is: no row, column, or 3×3 box contains the same digit twice. The board does not need to be solvable, just internally consistent.

Pattern: encode each constraint as a hashset key

Each filled cell participates in three constraints — its row, its column, its box. Encode each as a string key (or tuple) and throw them all into one set. Any duplicate key means a violated rule.

The solution

def is_valid_sudoku(board: list[list[str]]) -> bool:
    seen: set[str] = set()
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == '.':
                continue
            box = (r // 3, c // 3)
            keys = (
                f"row {r} = {v}",
                f"col {c} = {v}",
                f"box {box} = {v}",
            )
            for k in keys:
                if k in seen:
                    return False
                seen.add(k)
    return True

O(1) time and space — the board is fixed at 81 cells, so this is constant-bounded. The interesting bit is the encoding trick: by making the row/column/box keys textually distinct (with literal prefixes), one set can hold all three constraint families without collisions.

The 3×3 box index (r // 3, c // 3) maps every cell to one of nine boxes. Cell (4, 7) lands in box (1, 2), the middle-right box. Memorise this trick — it shows up in any "9-square Sudoku variant" question.

Edge cases

• All cells empty. Trivially valid — there are no filled cells to violate anything.
• Inputs aren't '1'..'9'. Real Sudoku boards enforce this; if the problem doesn't, add a digit-check inside the loop.
• Whitespace or other sentinels. Just check for '.' and assume everything else is a digit per the problem spec.

Related

• Sudoku Solver. Backtracking with this validator as the constraint check. Famously hard to write cleanly under time pressure.
• N-Queens. Same "encode each constraint as a set" trick (rows, two diagonals).