Sudoku

One assignability check, applied 27 times, lets the compiler verify a solved Sudoku board.

This one is based off a challenge from Advent of Typescript 2023 by TypeHero (Day 22), and they deserve the credit for the idea: write a type that verifies a Sudoku game is solved.

The board arrives as a 9x9 grid of digits, with each row pre-split into three 3-tuples, a shape that hints at the 3x3 boxes. Your SudokuSolved type must return true only when every row, every column and every 3x3 box contains all digits from 1 to 9. Along the way you'll learn how indexed access types distribute over tuples and unions, and how a single extends check can act as a type-level set comparison.

Detailed Explanation

Here it is in full:

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
 
type Trio = [Digits, Digits, Digits]
type Row = [Trio, Trio, Trio]
type Board = [Row, Row, Row, Row, Row, Row, Row, Row, Row]
 
type Idx = 0 | 1 | 2
 
type HasAllDigits<U> = [Digits] extends [U] ? true : false
 
type RowsValid<B extends Board> = {
  [R in keyof B]: HasAllDigits<B[R][number][number]>
}[number]
 
type ColumnsValid<B extends Board> = {
  [C in Idx]: { [O in Idx]: HasAllDigits<B[number][C][O]> }[Idx]
}[Idx]
 
type Bands<B extends Board> = [
  [B[0], B[1], B[2]],
  [B[3], B[4], B[5]],
  [B[6], B[7], B[8]],
]
 
type BoxesValid<B extends Board> = {
  [G in Idx]: {
    [C in Idx]: HasAllDigits<Bands<B>[G][number][C][number]>
  }[Idx]
}[Idx]
 
type SudokuSolved<B extends Board> = [
  RowsValid<B> | ColumnsValid<B> | BoxesValid<B>,
] extends [true]
  ? true
  : false

That looks like a lot, but it's one idea applied 27 times.

The key insight: 9 cells + 9 distinct digits = a union check

A row, column or box is valid exactly when its nine cells contain each digit from 1 to 9. Since there are nine cells and nine required digits, that's equivalent to saying: the union of the nine cell types is exactly 1 | 2 | ... | 9. If any digit repeats, another digit must be missing, and the union shrinks.

That's what HasAllDigits checks:

[object Object]

Wrapping both sides in a one-element tuple ([Digits] and [U]) is the idiomatic "compare unions as whole sets" pattern. Strictly speaking it's defensive here rather than required: conditional types only distribute when the type before extends is a naked type parameter, and Digits is a union alias, not a parameter, so a bare Digits extends U wouldn't split into per-digit checks anyway. The brackets cost nothing, though, and they both signal the intent and keep the check safe if a refactor ever puts a type parameter on the left. [Digits] extends [U] asks "does U include every digit?", which for a nine-cell union means "is this a perfect 1–9 set?".

A quick intermediate example:

type Good = HasAllDigits<1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9> // true
type Bad = HasAllDigits<1 | 2 | 3 | 4 | 5 | 6 | 7 | 8> // false (9 missing, something repeated)

So the whole challenge reduces to collecting the right nine-cell union for each of the 27 regions, and indexed access types do all the collecting.

Collecting rows: indexing a tuple with number

Indexing a tuple type with number yields the union of all its element types. A row in this challenge is [Trio, Trio, Trio], so B[R][number] is the union of its three trios, and B[R][number][number] is the union of all nine digits in the row:

type RowsValid<B extends Board> = {
  [R in keyof B]: HasAllDigits<B[R][number][number]>
}[number]

Because B is a type parameter, [R in keyof B] is a homomorphic mapped type, one that preserves the shape of its input (a tuple maps to a tuple) instead of producing a plain object. It maps only over the tuple positions 0–8 and produces a tuple of nine booleans. The final [number] collapses that tuple into a union: true if every row passed, boolean (i.e. true | false) if any row failed.

Collecting columns: indexing a union distributes

B[number] is the union of all nine rows. Indexed access distributes over a union, so B[number][C][O] picks trio C, cell O out of each row and unions the results. That is exactly column 3*C + O:

type ColumnsValid<B extends Board> = {
  [C in Idx]: { [O in Idx]: HasAllDigits<B[number][C][O]> }[Idx]
}[Idx]

The nested mapped types enumerate all 3 × 3 = 9 columns, and the two [Idx] lookups union the nine boolean results together.

Collecting boxes: regroup the rows into bands

A 3x3 box spans three consecutive rows. Bands regroups the board into three bands of three rows each:

type Bands<B extends Board> = [
  [B[0], B[1], B[2]],
  [B[3], B[4], B[5]],
  [B[6], B[7], B[8]],
]

Now Bands<B>[G][number] is the union of the three rows in band G, [C] picks trio C from each (distributing again), and the final [number] unions their cells: the nine digits of one box. One subtlety: BoxesValid maps with [G in Idx] rather than [G in keyof Bands<B>]. Since Bands<B> isn't a bare type parameter, mapping over its keyof wouldn't be homomorphic: keyof Bands<B> includes the array members 'length', 'map' and so on, so the mapped type would also try to evaluate Bands<B>[G][number][C][number] for G = 'length' and G = 'map', indexing into non-tuple members and breaking the type. Using the explicit Idx = 0 | 1 | 2 union sidesteps that entirely.

Combining 27 answers into one

Each of the three validators evaluates to a union of booleans: true if all its regions passed, boolean if any failed. The final type unions all three and does one last non-distributive check:

type SudokuSolved<B extends Board> = [
  RowsValid<B> | ColumnsValid<B> | BoxesValid<B>,
] extends [true]
  ? true
  : false

If even one of the 27 regions produced false, the union becomes true | false = boolean, and [boolean] extends [true] is false. The tuple wrapping here is convention rather than necessity: distribution only kicks in over a naked type parameter, and the left side is a union expression, so an unwrapped check would also evaluate to a clean false (boolean extends true fails on its own). The brackets make the "compare as one whole type" intent explicit.

Edge cases the tests cover

• A solved board with a single corrupted trio ([7, 9, 8] becomes [8, 9, 4]): the duplicated 4 and missing 7 break the affected row, two columns and one box at once, and any single failing region is enough to flip the verdict to false.
• A board built from cyclically shifted rows: every row and every column is a perfect 1–9 set, but the boxes aren't. Only BoxesValid catches it, which is why all three checks are genuinely necessary.
• Nine identical rows: each row passes, but every column is a single repeated digit, so its union has one member and HasAllDigits fails.

Once you see that "valid region" means "union equals Digits", the solution is three different ways of steering indexed access types to gather the right nine cells.