Several sets at once

When one element belongs to more than one group, the difficulty is index arithmetic, not algorithms.

Here it is on a small grid, checking only two constraints: no repeated value in any row, and none in any column.

1from collections import defaultdict2 3def rows_and_cols_ok(grid):4    rows = defaultdict(set)5    cols = defaultdict(set)6 7    for r in range(len(grid)):8        for c in range(len(grid[r])):9            value = grid[r][c]10            if value == ".":11                continue                      # blanks are not a constraint12            if value in rows[r] or value in cols[c]:13                return False14            rows[r].add(value)15            cols[c].add(value)16    return True17 18print(rows_and_cols_ok([["1", "2"], ["2", "1"]]))19print(rows_and_cols_ok([["1", "2"], ["1", "."]]))

Why it works

Naming a region with integer division

The interesting constraint is usually the third kind: a block, tile, or bucket that a coordinate falls into. Integer division is what turns a coordinate into a region name.

For blocks of size b, the cell at (r, c) sits in block (r // b, c // b). With b = 3, rows 0, 1, 2 collapse to block row 0, rows 3, 4, 5 to block row 1, and so on.

1for r, c in [(0, 0), (2, 1), (3, 4), (8, 8)]:2    print((r, c), "is in block", (r // 3, c // 3))

Where this returns

The same idea powers n-queens in Unit 10, where each queen constrains a column and two diagonals at once, and the diagonal names come from exactly this kind of index arithmetic. Get comfortable with it here, on a problem where the only difficulty is the bookkeeping.

Quick check· 5 min

Which cells share a block?

Using the block index (r // 3, c // 3), which of these pairs of cells sit in the same 3 by 3 block?

(0, 2) and (2, 0)(2, 2) and (3, 3)(4, 1) and (1, 4)(8, 8) and (5, 5)

Problem· 20 min

Valid Sudoku

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1from collections import defaultdict2 3def rows_and_cols_ok(grid):4 rows = defaultdict(set)5 cols = defaultdict(set)6 7 for r in range(len(grid)):8 for c in range(len(grid[r])):9 value = grid[r][c]10 if value == ".":11 continue # blanks are not a constraint12 if value in rows[r] or value in cols[c]:13 return False14 rows[r].add(value)15 cols[c].add(value)16 return True17 18print(rows_and_cols_ok([["1", "2"], ["2", "1"]]))19print(rows_and_cols_ok([["1", "2"], ["1", "."]]))