Valid Sudoku · Optimal Solution

Three dimensions, three hash sets, one linear pass.

A puzzle app validates a player's partially filled Sudoku board before accepting a submission. Each row, each column, and each 3×3 sub-box must contain the digits 1–9 without repetition — empty cells are placeholders and ignored entirely. Three sets of hash tables (one per dimension) and a single linear scan over all 81 cells detect any rule violation. O(1) time and O(1) space — the board size is fixed.

Interactive

Watch the algorithm run

Concept

Three HashSets per Dimension

We maintain three arrays of hash sets — rowDigits[9], columnDigits[9], and boxDigits[9] — 27 sets in total. As we scan each filled cell, we check whether its digit already exists in the corresponding row set, column set, or box set. If any of the three contains it, we have found a duplicate and the board is invalid. Otherwise we add the digit to all three sets and move on.

Algorithm

Box Index Formula

A single scan through all 81 cells, checking each filled digit against three hash sets — one per dimension. The box index is computed as (row / 3) × 3 + (col / 3).

  1. 1

    Create 27 hash sets

    Initialize rowDigits[9], colDigits[9], and boxDigits[9] — one set per row, column, and 3×3 box.

  2. 2

    Scan each filled cell

    Skip empty cells ('.'). For each digit, compute its row, column, and box index.

  3. 3

    Check for conflicts

    If the digit already exists in any of the three corresponding sets, the board is invalid — stop immediately.

  4. 4

    Insert into sets

    If no conflict, add the digit to all three sets and continue to the next cell.

Edge Cases

Why Empty Cells Are Skipped

Understanding boundary behavior is as important as the main algorithm path.

Empty cells are skipped

Empty cells carry no value that could conflict. Including them would be meaningless — we only validate filled digits.

Early termination

A single duplicate is enough to declare the board invalid. There is no reason to continue scanning once a conflict is found.

Complexity

Complexity

Time: O(1) — the board is always 9×9, so we visit at most 81 cells regardless of input.
Space: O(1) — 27 hash sets each holding at most 9 digits, bounded by a constant.