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