VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 02: Hashing

Lesson 2.6 of 12 in this moduleFree

Valid Sudoku

Check that a partly filled 9 × 9 board breaks no rule: from re-scanning each row, column and box for every cell, to three passes with sets, to one pass with tagged keys or 27 bitmasks. Then larger boards, validating constraints in data and why the fixed size makes everything O(1).

about 10 min 5 Python examples 2 quick checks

Problem. Given a 9 × 9 board with digits "1"–"9" and "." for empty cells, return True if no digit repeats in any row, any column, or any of the nine 3 × 3 boxes. (The board doesn't have to be solvable.)

text
row 0:  5 3 . | . 7 . | . . .
row 1:  6 . . | 1 9 5 | . . .
row 2:  . 9 8 | . . . | . 6 .
...

ML context. This is constraint validation over groups: check that no key repeats within each group, for several groupings at once. Data pipelines do exactly this: "each (user, day) appears once", "each sample id is unique within its split", "no label repeats within an annotation batch". The skill is choosing one key per constraint and checking them all in a single pass.


1. Step 1: Clarify

Question Answer Why it matters
Board size? Always 9 × 9 Every approach is technically O(1)
Must it be solvable? No, only no repeats Solving is a different problem (module 10)
Empty cells? ".", skip them Only filled cells are checked
Generalise to n × n? Ask: complexity then matters Use n for the analysis

Because the board is fixed, "O(1)" hides real differences. We'll analyse in terms of n (an n × n board with √n × √n boxes), so the comparisons are meaningful.


2. Step 2: Brute force: re-scan for every cell

For each filled cell, scan its row, column and box for another cell with the same digit.

python
def is_valid_brute(board):
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == ".":
                continue
            for k in range(9):
                if k != c and board[r][k] == d:          # same row
                    return False
                if k != r and board[k][c] == d:          # same column
                    return False
            br, bc = 3 * (r // 3), 3 * (c // 3)
            for i in range(br, br + 3):
                for j in range(bc, bc + 3):
                    if (i, j) != (r, c) and board[i][j] == d:   # same box
                        return False
    return True


VALID = [
    "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
    "7...2...6", ".6....28.", "...419..5", "....8..79",
]
board = [list(row) for row in VALID]
assert is_valid_brute(board)
board[0][0] = "8"                                        # 8 now repeats in column 0
assert not is_valid_brute(board)
print("re-scan works: O(n³) for an n × n board")

For an n × n board: n² cells × O(n) scan each = O(n³). For 9 × 9 that's a few thousand steps, which is nothing, but on a 100 × 100 board (or a big data table) the repetition hurts. The waste: each row, column and box is re-scanned once per cell in it.


3. Step 3: Optimise: remember what each group has seen

First principles: which group is a cell in?

Row r and column c are given. The box index needs a formula: boxes are 3 × 3 blocks numbered 0–8 left to right, top to bottom, so

text
box = (r // 3) * 3 + (c // 3)
a 9 by 9 board with its nine boxes shaded; the cell at row 4, column 7 holds 5 and belongs to row 4, column 7 and box (4 // 3) · 3 + 7 // 3 = 5.
Diagram— a 9 by 9 board with its nine boxes shaded; the cell at row 4, column 7 holds 5 and belongs to row 4, column 7 and box (4 // 3) · 3 + 7 // 3 = 5.

Optimisation 1: 27 sets, one pass

Keep a set of seen digits for each row, each column and each box. Each filled cell checks three sets and adds to them. Every cell is visited once: O(n²), which is optimal (each cell must be read).

the cell (4, 7) = 5 is read once and produces three checks: row 4 has a 5, column 7 has a 5, box 5 has a 5; the same keys fit in 27 sets, one set of tagged tuples, or 27 nine-bit masks.
Diagram— the cell (4, 7) = 5 is read once and produces three checks: row 4 has a 5, column 7 has a 5, box 5 has a 5; the same keys fit in 27 sets, one set of tagged tuples, or 27 nine-bit masks.
python
import random


def is_valid(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):
            d = board[r][c]
            if d == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                return False
            rows[r].add(d)
            cols[c].add(d)
            boxes[b].add(d)
    return True


def brute(board):
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == ".":
                continue
            if any(board[r][k] == d for k in range(9) if k != c):
                return False
            if any(board[k][c] == d for k in range(9) if k != r):
                return False
            br, bc = 3 * (r // 3), 3 * (c // 3)
            if any(board[i][j] == d for i in range(br, br + 3) for j in range(bc, bc + 3) if (i, j) != (r, c)):
                return False
    return True


rng = random.Random(44)
for _ in range(2000):
    board = [["." for _ in range(9)] for _ in range(9)]
    for _ in range(rng.randint(0, 20)):
        board[rng.randrange(9)][rng.randrange(9)] = str(rng.randint(1, 9))
    assert is_valid(board) == brute(board)
print("27 sets, one pass: O(n²) time, O(n²) space; matches brute force on 2,000 boards")

Optimisation 2: one set of tagged keys

Instead of 27 sets, put tagged tuples into one set: ("row", r, d), ("col", c, d), ("box", b, d). Each tuple names one constraint. Simple to extend: a new rule is a new tag.

python
def is_valid_tagged(board):
    seen = set()
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == ".":
                continue
            keys = (("row", r, d), ("col", c, d), ("box", (r // 3) * 3 + c // 3, d))
            if any(k in seen for k in keys):
                return False
            seen.update(keys)
    return True


VALID = [
    "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
    "7...2...6", ".6....28.", "...419..5", "....8..79",
]
board = [list(row) for row in VALID]
assert is_valid_tagged(board)
board[4][7] = "3"                                    # 3 repeats in row 4 (and box 5)
assert not is_valid_tagged(board)
print("tagged keys: one set, one key per constraint")

Optimisation 3: bitmasks (constant factors)

With only 9 digits, each group's "seen" set fits in 9 bits of an integer. mask & (1 << d) checks a digit; mask |= 1 << d adds it. Same O(n²) time, but 27 small integers instead of 27 hash sets: much less memory and no hashing.

python
def is_valid_bits(board):
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            if board[r][c] == ".":
                continue
            bit = 1 << (int(board[r][c]) - 1)
            b = (r // 3) * 3 + c // 3
            if rows[r] & bit or cols[c] & bit or boxes[b] & bit:
                return False
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
    return True


VALID = [
    "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
    "7...2...6", ".6....28.", "...419..5", "....8..79",
]
assert is_valid_bits([list(row) for row in VALID])
print("bitmasks: 27 integers, no hashing")

Quick check

Why is cell (r, c) in box (r // 3) * 3 + c // 3?

  1. It's a convention with no reason
  2. r // 3 gives the band of boxes (0, 1 or 2) and c // 3 the stack within it; each band holds 3 boxes, so the box number is band × 3 + stack
  3. Because there are 9 boxes
  4. It works only for the centre box
Show the answer

B. r // 3 gives the band of boxes (0, 1 or 2) and c // 3 the stack within it; each band holds 3 boxes, so the box number is band × 3 + stack — Integer division by the box size maps each row and column to its box coordinate; combining them row-major gives 0–8.


4. When the constraints change

If the constraint becomes… Best approach Time Space
Fixed 9 × 9 Any of the above: all O(1) O(1) O(1)
n × n board, clarity first Re-scan per cell O(n³) O(1)
n × n board One pass with sets per group O(n²) O(n²)
Small digit range Bitmasks per group O(n²) O(n) integers
Extra rules (e.g. diagonals) One more tagged key per cell O(n²) O(n²)
Also solve the board Backtracking + these checks (module 10) exponential worst case O(n²)
Uniqueness rules in a data table Group-by keys, then count duplicates O(rows) O(distinct keys)

Change A: uniqueness constraints in a dataset

"Each (user_id, day) appears at most once, and each event_id is globally unique." That's two constraints, so two tagged keys per row, checked in one pass. The same code shape as tagged Sudoku.

python
def find_violations(rows):
    seen, bad = set(), []
    for i, row in enumerate(rows):
        keys = (("user_day", row["user"], row["day"]), ("event", row["event_id"]))
        for k in keys:
            if k in seen:
                bad.append((i, k[0]))
            seen.add(k)
    return bad


events = [
    {"user": "u1", "day": "mon", "event_id": 1},
    {"user": "u2", "day": "mon", "event_id": 2},
    {"user": "u1", "day": "mon", "event_id": 3},     # u1 twice on Monday
    {"user": "u3", "day": "tue", "event_id": 2},     # event id 2 reused
]
assert find_violations(events) == [(2, "user_day"), (3, "event")]
print("each constraint is one tagged key: one pass over the data")

Quick check

Your table must satisfy three uniqueness rules. What's the one-pass approach?

  1. For each row, build one tagged key per rule and check them against a single seen set
  2. Sort by each rule and scan three times
  3. Compare every pair of rows
  4. Use three nested loops
Show the answer

A. For each row, build one tagged key per rule and check them against a single seen set — One key per constraint turns several uniqueness checks into one pass of set lookups.


5. Saying it out loud

"Re-scanning the row, column and box for every cell is O(n³) on an n × n board. Instead I remember what each group has seen: 27 sets, with the box index (r // 3) * 3 + c // 3. Each filled cell checks and updates three sets, so one pass, O(n²), which is optimal. For a fixed 9 × 9 board everything is O(1), so I'd mention that, and use bitmasks if I wanted small constants."


Check yourself

  1. Why analyse with n when the board is always 9 × 9?
  2. What's the repeated work in the re-scan approach?
  3. Derive the box index formula.
  4. What are the three keys a filled cell produces?
  5. What do bitmasks improve, and what don't they change?
  6. How does the tagged-key idea apply to data validation?
Answers
  1. With a fixed size, everything is O(1); using n exposes the real differences between approaches.
  2. Each row, column and box is scanned again for every cell in it.
  3. r // 3 is the box row (band), c // 3 the box column; number row-major: (r // 3) * 3 + c // 3.
  4. (row r, digit), (column c, digit), (box b, digit).
  5. Memory and constant factors (27 integers, no hashing); the time complexity stays O(n²).
  6. Each uniqueness rule becomes a tagged key per row, all checked against one seen set in a single pass.