Valid Sudoku

A Sudoku validator does not solve the puzzle. It tracks whether the digits already placed violate any row, column, or 3×3 box constraint.

Read the contract first

Given a 9×9 board, return true when the filled cells contain no duplicate digit in any of these scopes:

1. The cell's row
2. The cell's column
3. The 3×3 sub-box containing the cell

A cell contains either a digit from '1' through '9' or '.', which represents an empty position. Empty cells are ignored.

That means a board can be valid while it is incomplete. Validation checks the current assignments; it does not fill cells, prove that a solution exists, or require every row to contain all nine digits.

The answer direction for a Valid Sudoku solution is straightforward: scan each cell once, skip blanks, and check the digit against three sets—one for its row, one for its column, and one for its box.

Turn the rules into three obligations

For a cell at (row, col) with value value, ask three independent questions:

• Has value already appeared in this row?
• Has value already appeared in this column?
• Has value already appeared in this box?

Each question has the same shape: has this item appeared in this scope? A set represents that obligation directly. Membership is an average O(1) operation, so we do not need to rescan a row, column, or box whenever we encounter a digit.

The scope belongs in the state. A '5' in row 0 and a '5' in row 4 can be legal, so one global set would reject valid boards. Instead, maintain separate sets:

rows[row]
columns[col]
boxes[box]

rows[row] records digits seen in one row, columns[col] records digits seen in one column, and boxes[box] records digits seen in one 3×3 box. This is the core hash sets coding interview pattern: store membership at the level where the constraint applies.

Start with the obvious baseline

A clean first approach performs three groups of passes:

1. Scan every row with a fresh set.
2. Scan every column with a fresh set.
3. Scan each 3×3 box with a fresh set.

For each scope, skip '.', reject a digit already in the set, and otherwise add it.

This baseline is useful because each traversal mirrors one rule. It is easy to explain and gives you a reference implementation. But it revisits the board and duplicates traversal logic. The better organization keeps the same three checks while letting one visit to a cell update all three scopes.

The optimization is therefore not a new Sudoku rule. It is a better arrangement of the same obligations.

Map each cell to its box

Rows and columns already have direct indexes. The only extra coordinate work is finding the 3×3 box.

Integer division groups a cell into its box row and box column:

box_row = row // 3
box_col = col // 3

There are three boxes across each box row, so flatten those two coordinates into one index:

box = (row // 3) * 3 + (col // 3)

For (row, col) = (5, 7):

box = (5 // 3) * 3 + (7 // 3)
     = 1 * 3 + 2
     = 5

The cell belongs to box 5 under zero-based numbering.

This formula is worth deriving rather than memorizing. row // 3 identifies which horizontal band contains the cell. col // 3 identifies which box within that band contains it. Multiplying the band by 3 moves to the correct block of box indexes; adding the within-band position finishes the mapping.

Derive the one-pass algorithm

Initialize nine sets for each type of scope:

rows = [set() for _ in range(9)]
columns = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]

For each cell:

1. Read its value.
2. Skip it if the value is '.'.
3. Compute the cell's box index.
4. Check the value in the corresponding row, column, and box sets.
5. Return False if it appears in any of them.
6. Add it to all three sets.

The sets are persistent state, not temporary scratch space. After part of the board has been processed, each set summarizes the filled digits already observed in its scope.

Invariant: Before processing a cell, every row, column, and box set contains exactly the filled digits encountered earlier in that scope, with no duplicates.

If the current value already appears in one set, the matching Sudoku rule is violated and returning False is final. If it appears in none of them, adding it to all three sets preserves the invariant for the next cell. If the scan reaches the end, no filled digit repeated in any tracked scope, so the board is valid.

Early exit is safe: a duplicate cannot be repaired by cells later in the scan.

Implement it in Python

Here is a direct Valid Sudoku Python implementation:

def is_valid_sudoku(board: list[list[str]]) -> bool:
    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):
            value = board[row][col]

            if value == ".":
                continue

            box = (row // 3) * 3 + (col // 3)

            if (
                value in rows[row]
                or value in columns[col]
                or value in boxes[box]
            ):
                return False

            rows[row].add(value)
            columns[col].add(value)
            boxes[box].add(value)

    return True

Each state variable has one job:

• rows[row] enforces row uniqueness.
• columns[col] enforces column uniqueness.
• boxes[box] enforces box uniqueness.
• box translates cell coordinates into the third constraint scope.

I prefer this explicit version in an interview. The code follows the proof closely, so a reviewer can see which obligation each collection enforces. The function also leaves the input board unchanged, keeping validation separate from mutation.

Trace the state through a cell

Suppose the scan reaches this cell:

row = 5
col = 7
value = "8"

Its box is:

box = (5 // 3) * 3 + (7 // 3)
     = 5

Imagine the current state is:

rows[5]    = {"7", "2", "6"}
columns[7] = {"3", "8"}
boxes[5]   = {"6", "8"}

The value is new to the row but already present in the column and box. The board is invalid. This is why the checks must be independent: passing one scope does not imply passing the others.

For a blank cell, the transition is different:

value = "."

The algorithm skips it, performs no membership test, and changes no set. Treating '.' as a digit would create false duplicates whenever multiple cells were empty.

A valid filled cell updates all three ledgers:

rows[row].add(value)
columns[col].add(value)
boxes[box].add(value)

One observation, three state updates. That is the whole engine.

Complexity and edge cases

The specified board always contains 81 cells, so the fixed-size problem has constant bounds:

Time:  O(1)
Space: O(1)

Those bounds describe the contract, not the shape of the algorithm. If the problem were generalized to an n × n board with compatible sub-boxes, the scan would process n² cells, giving O(n²) time. The row, column, and box membership state would also grow with the board, commonly described as O(n²) auxiliary space for the full collection.

Test the cases that expose the usual mistakes:

• A duplicate in one row
• A duplicate in one column
• A duplicate inside one 3×3 box
• An all-blank board
• A sparse, incomplete board with no duplicates
• A digit that is new to its row but repeated in its column
• A digit that is new to its row and column but repeated in its box

Before submitting, recheck four implementation details:

• Skip '.' before inserting into any set.
• Use row // 3 and col // 3 to identify box groups.
• Keep the box formula grouped as (row // 3) * 3 + (col // 3).
• Do not require every scope to contain all nine digits.

Under the supplied constraints, you also do not need to add shape or symbol validation. The input is guaranteed to be a 9×9 board containing digits or '.'.

The transferable pattern

When one item must satisfy several independent membership constraints, give each scope its own state and update every relevant scope in one scan.

For Sudoku, name the scopes first: row, column, box. Then define what each set means, derive the coordinate mapping, state the invariant, and implement the smallest transition that preserves it.

The reusable move is simple: identify overlapping views of the same item, track membership separately in each view, and reject the first conflict. Once you see that structure, many matrix-validation problems stop looking like a maze of loops and start looking like one disciplined state-tracking pass.