Valid Sudoku

A Sudoku board has three kinds of rule: no digit twice in a row, no digit twice in a column, no digit twice in any of the nine 3×3 boxes. Checking a half-filled board against those rules is a seen-set problem — just with 27 sets instead of one.

Interviewers ask it because it tests two small but real skills: organising several sets cleanly, and mapping a cell to its box without a chain of if statements. It also invites a good conversation about complexity, since the board is always 9×9.

The problem

You are given a 9×9 board as a list of 9 rows. Each cell holds a digit "1" to "9" or "." for empty. Return True if no digit repeats within any row, any column, or any of the nine 3×3 boxes. Only the filled cells are checked. The board does not need to be solvable.

Here is a sparse board, written one row per string:

row 0:  8 . . | . 4 . | . . 2row 1:  . . 3 | . . . | 7 . .row 2:  . 3 . | . . 1 | . . .        ------+-------+------row 3:  . . 5 | . . . | . . .row 4:  . . . | . 6 . | . 1 .row 5:  1 . . | . . . | . . 9        ------+-------+------row 6:  . . . | 7 . . | . . .row 7:  . . . | . . . | . 4 .row 8:  2 . . | . . . | 8 . .

• This board → False. The digit 3 appears at row 1, column 2 and at row 2, column 1. They are in different rows and different columns, but both sit in the top-left box.
• The same board with the 3 at row 2, column 1 replaced by 5 → True.

Constraints: always 9×9; cells are "1"–"9" or ".".

Clarifying questions

• Must the board be solvable? No. Only the filled cells are checked against the three rules.
• Are the cells strings or integers? Strings, with "." for empty. Compare strings; do not convert.
• Could there be characters other than digits and dots? Assume not.

Approach 1: scan the row, column and box of every filled cell

For each filled cell, look along its row, down its column, and around its 3×3 box for the same digit.

1def is_valid_sudoku_brute(board: list[list[str]]) -> bool:2    """For every filled cell, scan its row, column and box for the same digit."""3    for r in range(9):4        for c in range(9):5            digit = board[r][c]6            if digit == ".":7                continue8            for i in range(9):9                if i != c and board[r][i] == digit:10                    return False11                if i != r and board[i][c] == digit:12                    return False13            top, left = 3 * (r // 3), 3 * (c // 3)14            for rr in range(top, top + 3):15                for cc in range(left, left + 3):16                    if (rr, cc) != (r, c) and board[rr][cc] == digit:17                        return False18    return True

Be honest about the cost. The board is always 81 cells, so this does at most 81 × 27 ≈ 2,200 comparisons — a constant. It is not "too slow" in any practical sense. The reason to improve it is what happens if the board grows: on an n × n board (n = 9 here, with √n × √n boxes), each of the n² cells scans about 3n others, which is O(n³). It also compares the same pairs of cells many times over.

The key insight

Every filled cell belongs to exactly one row, one column and one box. So keep one seen-set for each row, each column and each box — 27 sets — and visit every cell once. A cell is fine if its digit is in none of its three sets; then add the digit to all three.

The only question left is which box a cell is in. Number the boxes 0 to 8, left to right and top to bottom. Row r is in band r // 3 (0, 1 or 2) and column c is in stack c // 3. So:

box = (r // 3) * 3 + c // 3            c 0-2   c 3-5   c 6-8r 0-2         0       1       2r 3-5         3       4       5r 6-8         6       7       8

For the cell at row 2, column 1: (2 // 3) * 3 + 1 // 3 = 0 * 3 + 0 = 0, the top-left box.

Approach 2: one pass with 27 seen-sets

1def is_valid_sudoku(board: list[list[str]]) -> bool:2    """One pass: 27 seen-sets, one per row, column and box."""3    rows = [set() for _ in range(9)]4    cols = [set() for _ in range(9)]5    boxes = [set() for _ in range(9)]6    for r in range(9):7        for c in range(9):8            digit = board[r][c]9            if digit == ".":10                continue11            box = (r // 3) * 3 + c // 312            if digit in rows[r] or digit in cols[c] or digit in boxes[box]:13                return False14            rows[r].add(digit)15            cols[c].add(digit)16            boxes[box].add(digit)17    return True

This is the seen-set template three times over: check all three sets, then add to all three. Note [set() for _ in range(9)] rather than [set()] * 9 — the second makes nine references to one set.

Dry run on the example board, in reading order, up to the point where it stops:

The row check (row 2 holds no 3 yet) and the column check (column 1 holds no 3 yet) both pass. Only the box set catches it, which is why forgetting the boxes is a real bug, not a style issue.

Time: O(n²) on an n × n board — each of the 81 cells is visited once with a constant number of set operations, at most 243 lookups here. Space: O(n²) — 27 sets holding at most 9 digits each, 243 entries in total.

A common alternative is three separate passes: check every row with a fresh set, then every column, then every box. It is also O(n²) and some people find it easier to get right, because each pass does one thing. The one-pass version is shorter and stops at the first conflict wherever it is; either is a good answer if you explain why each cell is looked at a constant number of times.

Approach 3: one set of labelled tuples

Instead of 27 sets, keep one set of facts like ("row", 2, "3"), ("col", 1, "3") and ("box", 0, 0, "3"). A cell is valid if none of its three facts is already present.

1def is_valid_sudoku_one_set(board: list[list[str]]) -> bool:2    """One set of labelled tuples instead of 27 sets."""3    seen: set[tuple] = set()4    for r in range(9):5        for c in range(9):6            digit = board[r][c]7            if digit == ".":8                continue9            keys = [("row", r, digit), ("col", c, digit), ("box", r // 3, c // 3, digit)]10            if any(key in seen for key in keys):11                return False12            seen.update(keys)13    return True

Same complexity, fewer containers, and the box can be named by its (band, stack) pair so no formula is needed. Some interviewers find this the clearest; others prefer the explicit arrays. Either is fine if you can explain it.

Edge cases

• Empty board: every cell is skipped; True.
• A full, correctly solved board: 81 cells, no conflicts; True.
• A conflict only in a box (like the example): only the box check catches it.
• A board that is valid but unsolvable: still True. The problem checks rules, not solvability — say so out loud.

Follow-ups

• Solve the board: backtracking — try each digit in an empty cell, keep the 27 sets as the fast validity check, undo on failure. The Backtracking section covers it.
• An n × n board: replace 3 with b = int(n ** 0.5) everywhere: box = (r // b) * b + c // b.
• Less memory: use 27 integers as bitmasks, one bit per digit. mask & (1 << d) tests, mask |= 1 << d adds. Same logic in 27 machine words.