2026-09-25 — Valid Sudoku

Difficulty: 🟢 Easy Pattern: Constrained counting — one set (or counter) per row, column and box Time-box: 20 minutes

Problem

Given a 9×9 sudoku board represented as a list of 9 lists of characters, decide whether the partially filled board is valid. A board is valid when no digit 1–9 appears twice in the same row, the same column, or the same 3×3 sub-box. Cells that are empty are represented by '.' and are ignored.

The board does not have to be solvable — you are only checking that the digits currently placed do not already contradict each other.

Examples

board with 5 at (0,0) and 5 at (1,2)  -> False   # same 3x3 box, different row AND column
board with 8 at (4,0) and 8 at (4,7)  -> False   # same row
a fully solved (or partially filled) board -> True
empty board (all '.')                  -> True   # nothing contradicts anything

Constraints

The board is always 9×9.
Every cell is a character '1'–'9' or '.'.
You only validate the entries that are present; a correct unfinished board is valid.

Hint (open only if stuck after 10 minutes)

Sweep all 81 cells once. For a filled cell, you need to ask three yes/no questions: "has this row already seen this digit?", and the same for column and 3×3 box. What gives each of those questions a constant-time answer? (How do you compute a cell's box index from r and c?)

Solution

def is_valid_sudoku(board):
    rows  = [set() for _ in range(9)]
    cols  = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == ".":
                continue
            box = (r // 3) * 3 + c // 3
            if v in rows[r] or v in cols[c] or v in boxes[box]:
                return False
            rows[r].add(v)
            cols[c].add(v)
            boxes[box].add(v)

    return True

How it works. One left-to-right sweep; each filled cell is checked against the three containers for its row, column and box, then inserted into them. Because insertion happens after the check, a value colliding with an earlier cell is the exact moment of contradiction, and the first such cell is an immediate False. The box index (r // 3) * 3 + c // 3 maps rows 0–2/3–5/6–8 and columns 0–2/3–5/6–8 onto the 9 boxes in reading order.

Complexity. Time: O(1) — the board is fixed at 81 cells, so the sweep is a constant 81 constant-time set operations (in asymptotic interview language: O(n²) in the board side length n, O(1) for a real sudoku). Space: O(1) — 27 sets holding at most 81 characters total.

Edge cases that matter.

The empty board: every cell is skipped, all containers stay empty, True.
A single filled cell: trivially valid.
The same digit appearing twice in different rows, columns and boxes: perfectly legal (every digit appears nine times in a solved board).
A duplicate that shares neither row nor column but shares a box: this is the only case a row/column-only check misses.
Large digits: only '1'–'9' occur, so there is no overflow angle.

Common wrong answer. Two plausible ones:

Check rows and columns only. The board with 5 at (0, 0) and 5 at (1, 2) passes it — same top-left box, different row and column — and is the input that exposes the bug.

bad = [["."] * 9 for _ in range(9)]
bad[0][0] = "5"
bad[1][2] = "5"
# row/col-only validator: True   <- wrong, box violated
# correct validator:              False

Verify each row contains exactly the digits 1–9. That describes a solved board. Any correct unfinished board — which the problem explicitly allows — has rows with missing digits, so this rejects valid input. The check you actually want is "no digit twice", never "all nine present".

Found a mistake? Edit this page on GitHub.