Valid Sudoku

Sudoku is a famous paper and pencil game. The goal of Sudoku is to fill a 9x9 grid with numbers so that each row, column and 3x3 section contain all of the digits between 1 and 9. You'll be given a finished 9x9 grid, and you need to determine if it's a valid Sudoku solution. Return true if it is, and false if it is not. Unlike the sibling Sudoku challenge, the grid here is a flat 9x9 matrix, so you have to carve out the 3x3 boxes yourself. That makes it a solid workout for indexed access types and non-distributive union checks.

type Matrix = [
  [9, 5, 7, 8, 4, 6, 1, 3, 2],
  [2, 3, 4, 5, 9, 1, 6, 7, 8],
  [1, 8, 6, 7, 3, 2, 5, 4, 9],
  [8, 9, 1, 6, 2, 3, 4, 5, 7],
  [3, 4, 5, 9, 7, 8, 2, 6, 1],
  [6, 7, 2, 1, 5, 4, 8, 9, 3],
  [4, 6, 8, 3, 1, 9, 7, 2, 5],
  [5, 2, 3, 4, 8, 7, 9, 1, 6],
  [7, 1, 9, 2, 6, 5, 3, 8, 4]
]
type result = ValidSudoku<Matrix>; // expected to be true

type Matrix = [
[9, 5, 7, 8, 4, 6, 1, 3, 2],
[2, 3, 4, 5, 9, 1, 6, 7, 8],
[1, 8, 6, 7, 3, 2, 5, 4, 9],
[8, 9, 1, 6, 2, 3, 4, 5, 7],
[3, 4, 5, 9, 7, 8, 2, 6, 1],
[6, 7, 2, 1, 5, 4, 8, 9, 3],
[4, 6, 8, 3, 1, 9, 7, 2, 5],
[5, 2, 3, 4, 8, 7, 9, 1, 6],
[7, 1, 9, 2, 6, 5, 3, 8, 4]
]
type result = ValidSudoku <Matrix>; // expected to be true

Detailed Explanation

Start from the finished code:

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
 
type Group = [0 | 1 | 2, 3 | 4 | 5, 6 | 7 | 8]
type Idx = Group[number]
 
type HasAllDigits<U> = [Digits] extends [U] ? true : false
 
type RowsValid<M extends number[][]> = {
  [R in Idx]: HasAllDigits<M[R][number]>
}[Idx]
 
type ColumnsValid<M extends number[][]> = {
  [C in Idx]: HasAllDigits<M[number][C]>
}[Idx]
 
type Band = 0 | 1 | 2
 
type BoxesValid<M extends number[][]> = {
  [R in Band]: {
    [C in Band]: HasAllDigits<M[Group[R]][Group[C]]>
  }[Band]
}[Band]
 
type ValidSudoku<M extends number[][]> = [
  RowsValid<M> | ColumnsValid<M> | BoxesValid<M>,
] extends [true]
  ? true
  : false

The trick that makes this whole solution short: a nine-cell region is valid exactly when the union of its cell types equals 1 | 2 | ... | 9. Nine cells, nine required digits. If anything repeats, something else is missing and the union shrinks. So every row, column and box check boils down to "gather the right nine cells as a union, then compare it against Digits".

HasAllDigits: comparing unions as sets

[object Object]

Both sides are wrapped in one-element tuples, the idiomatic "compare unions wholesale" pattern. Here it's defensive 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 either. The brackets document the intent and keep the check safe under future refactoring. [Digits] extends [U] is true exactly when U contains every digit from 1 to 9.

type Yes = HasAllDigits<1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9> // true
type No = HasAllDigits<1 | 2 | 3 | 4 | 5 | 6 | 7 | 8> // false

Rows: M[R][number]

Indexing a tuple type with number produces the union of all its element types. So for row R, M[R][number] is the union of its nine cells:

type RowsValid<M extends number[][]> = {
  [R in Idx]: HasAllDigits<M[R][number]>
}[Idx]

Idx is 0 | 1 | ... | 8 (derived from Group with the same [number] trick: Group[number] unions its three entries). The mapped type computes one boolean per row, and the trailing [Idx] look-up unions all nine booleans: true if every row passed, true | false (= boolean) if any failed.

Columns: indexed access distributes over unions

There's no "column tuple" in the input, but you don't need one. M[number] is the union of all nine rows, and indexed access distributes over a union:

// M[number]     = Row0 | Row1 | ... | Row8
// M[number][4]  = Row0[4] | Row1[4] | ... | Row8[4]

So M[number][C] is the union of the nine cells in column C, which makes the column check a one-liner:

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

Boxes: index with a union of indices

The same distribution trick carves out the 3x3 boxes. Group maps a band number to the union of the three indices it covers:

type Group = [0 | 1 | 2, 3 | 4 | 5, 6 | 7 | 8]
// Group[0] = 0 | 1 | 2, Group[1] = 3 | 4 | 5, Group[2] = 6 | 7 | 8

Indexing M with a union of row indices gives the union of those three rows; indexing that with a union of column indices gives the union of all nine cells in the box:

// M[0 | 1 | 2]            = Row0 | Row1 | Row2
// M[0 | 1 | 2][3 | 4 | 5] = the 9 cells of the top-middle box, as a union

BoxesValid iterates R and C over the three bands each, covering all nine boxes with two small nested mapped types. No arithmetic, no tuple slicing: the union does the slicing for you.

The final verdict

Each validator yields true when all its regions passed and boolean when any produced false. The last step unions all 27 answers and makes one non-distributive check:

type ValidSudoku<M extends number[][]> = [
  RowsValid<M> | ColumnsValid<M> | BoxesValid<M>,
] extends [true]
  ? true
  : false

If a single region failed, the union is boolean, and [boolean] extends [true] is false. As in HasAllDigits, the tuple wrapping is convention rather than necessity: the left side is a union expression, not a naked type parameter, so it wouldn't distribute even unwrapped; boolean extends true evaluates to false on its own. The brackets just make the whole-type comparison explicit.

Edge cases the tests cover

• Matrix2 differs from a valid board by swapping two adjacent cells in one row (1, 6, 7 vs 1, 7, 6). Every row still contains 1–9, so only the column check catches it. An adjacent swap corrupts two columns at once: here column 4 gets two 6s and no 7, column 5 two 7s and no 6. The box check stays green because both swapped cells sit inside the same 3x3 box; only a swap straddling a box boundary would trip BoxesValid too.
• Matrix3 is built from cyclically shifted rows: all rows and all columns are perfect 1–9 sets, but every 3x3 box repeats digits. Only the box check fails, proving all three region checks are truly independent.

The pattern to take away: indexed access with number or with a union of literal indices is a type-level "select these elements and union them" operator, and comparing unions with [A] extends [B] turns that into set logic.