Type Challenges: 31797-hard-sudoku Solution

Approach

Get all the elements in the row as union type
Check if the union type has all the numbers from 1 to 9 (i.e no duplicates) by Digits extends Foo ? true : false
Repeat the process for all rows, columns, and subgrids
Combine the results

Code

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
type Row = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
type Col = {
	C0: [Row, 0, 0]
	C1: [Row, 0, 1]
	C2: [Row, 0, 2]
	C3: [Row, 1, 0]
	C4: [Row, 1, 1]
	C5: [Row, 1, 2]
	C6: [Row, 2, 0]
	C7: [Row, 2, 1]
	C8: [Row, 2, 2]
}

type Subgrid = {
	S0: [0 | 1 | 2, 0, 0 | 1 | 2]
	S1: [0 | 1 | 2, 1, 0 | 1 | 2]
	S2: [0 | 1 | 2, 2, 0 | 1 | 2]
	S3: [3 | 4 | 5, 0, 0 | 1 | 2]
	S4: [3 | 4 | 5, 1, 0 | 1 | 2]
	S5: [3 | 4 | 5, 2, 0 | 1 | 2]
	S6: [6 | 7 | 8, 0, 0 | 1 | 2]
	S7: [6 | 7 | 8, 1, 0 | 1 | 2]
	S8: [6 | 7 | 8, 2, 0 | 1 | 2]
}

type SudokuSolved<T extends Array<number[][]>> =
	{
		[R in Row as `R${R}`]: Digits extends T[R][number][number] ? true : false
	} & {
		[C in keyof Col]: Digits extends T[Col[C][0]][Col[C][1]][Col[C][2]] ? true : false
	} & {
		[S in keyof Subgrid]: Digits extends T[Subgrid[S][0]][Subgrid[S][1]][Subgrid[S][2]] ? true : false
	} extends Record<string, true>
		? true
		: false

Solution by satohshi #35332

type RN = [number];
type R13 = [0, 1, 2];
type R19 = [0, 1, 2, 3, 4, 5, 6, 7, 8];
type R33 = [0 | 1 | 2,  3 | 4 | 5,  6 | 7 | 8];

type Values = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;

type Check<M extends number[][][], RI extends number[], RJ extends number[], RK extends number[]> = {
  [I in keyof RI]: {
    [J in keyof RJ]: {
      [K in keyof RK]: Values extends M[RI[I]][RJ[J]][RK[K]] ? true : false;
    }[number];
  }[number];
}[number];

type SudokuSolved<
  M extends number[][][]
> = false extends Check<M, R19, RN, RN> | Check<M, RN, R13, R13> | Check<M, R33, R13, RN> ? false : true;

Solution by alexandroppolus #35323

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
type G1 = [0, 1, 2];
type G2 = [3, 4, 5];
type G3 = [6, 7, 8];

type IsPass<T extends number[]> = Digits extends T[number] ? true : false;
type Flatten<T extends number[][][]> = T extends [[infer G1 extends number[], infer G2 extends number[], infer G3 extends number[]], ...infer R extends number[][][]] ?
  [[...G1, ...G2, ...G3], ...Flatten<R>] : [];

type ColCollector<T extends number[][], CI extends number, _I extends 1[] = []> =
  _I[`length`] extends 9 ? [] : [T[_I[`length`]][CI], ...ColCollector<T, CI, [..._I, 1]>];
type GridCollector<T extends number[][][], CI extends number, _I extends 1[] = [],
  _ColIndex extends number = [0, 1, 2, 0, 1, 2, 0, 1, 2][CI],
  _RowIndex extends number = [G1, G1, G1, G2, G2, G2, G3, G3, G3][CI][_I[`length`]]> =
  _I[`length`] extends 3 ? [] : [...T[_RowIndex][_ColIndex], ...GridCollector<T, CI, [..._I, 1]>];

type RowChecker<T extends number[][][]> = T extends [[infer G1 extends number[], infer G2 extends number[], infer G3 extends number[]], ...infer R extends number[][][]] ?
  IsPass<[...G1, ...G2, ...G3]> extends true ? RowChecker<R> : false :
  true;
type ColChecker<T extends number[][][], _IndexCounter extends 1[] = [], _Flatten extends number[][] = Flatten<T>> =
  _IndexCounter[`length`] extends 9 ? true :
  IsPass<ColCollector<_Flatten, _IndexCounter[`length`]>> extends true ? ColChecker<T, [..._IndexCounter, 1], _Flatten> : false;
type GridChecker<T extends number[][][], _IndexCounter extends 1[] = []> =
  _IndexCounter[`length`] extends 9 ? true :
  IsPass<GridCollector<T, _IndexCounter[`length`]>> extends true ? GridChecker<T, [..._IndexCounter, 1]> : false;

type SudokuSolved<T extends number[][][]> = RowChecker<T> | ColChecker<T> | GridChecker<T> extends true ? true : false;

Solution by E-uler #34717

type VerRows<T> = T extends [ infer F, ...infer R ]
  ? F extends [ [ infer A, infer B, infer C ], [ infer D, infer E, infer F ], [ infer G, infer H, infer I ] ]
    ? Digits extends [A, B, C, D, E, F, G, H, I][number]
      ? VerRows<R>
      : false
    : never
  : true

type UndefHelper<T> = T extends undefined ? unknown : T
type VerCols<T, _R extends unknown[] = [], > = T extends [ infer F, ...infer R ]
  ? F extends [ [ infer A extends UndefHelper<_R[0]>, infer B extends UndefHelper<_R[1]>, infer C extends UndefHelper<_R[2]> ],
                [ infer D extends UndefHelper<_R[3]>, infer E extends UndefHelper<_R[4]>, infer F extends UndefHelper<_R[5]> ],
                [ infer G extends UndefHelper<_R[6]>, infer H extends UndefHelper<_R[7]>, infer I extends UndefHelper<_R[8]> ]
              ]
    ? VerCols<R, [ _R[0] | A, _R[1] | B, _R[2] | C, _R[3] | D, _R[4] | E, _R[5] | F, _R[6] | G, _R[7] | H, _R[8] | I ]>
    : _R
  : true

type VerGrids<T> = T extends [
  [ infer A extends Digits[], ...infer RA ],
  [ infer B extends Digits[], ...infer RB ],
  [ infer C extends Digits[], ...infer RC ],
  ...infer R
] ? Digits extends A[number] | B[number] | C[number] 
  ? VerGrids<[ [RA], [RB], [RC], ...R ]>
  : false
: true

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
type SudokuSolved<T> = VerRows<T> extends false ? false : VerCols<T> extends false ? false : VerGrids<T> extends false ? false : true

Solution by lvjiaxuan #33613

Challenge 31797 - Sudoku

type Digit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

type Group = [Digit, Digit, Digit]
type Row = [Group, Group, Group]
type Grid = [Row, Row, Row, Row, Row, Row, Row, Row, Row]

type RowGroups = [0, 0, 0, 1, 1, 1, 2, 2, 2]
type GroupNrs = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]

type Index3 = 0 | 1 | 2
type Index9 = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

type Coord = `${Index9}${Index3}${Index3}`

type IdCoord<Crd = Coord> =
  Crd extends `${infer R extends Index9}${infer G extends Index3}${infer C extends Index3}`
  ? `R${R}:${Crd}` | `C${GroupNrs[G][C]}:${Crd}` | `G${GroupNrs[RowGroups[R]][G]}:${Crd}` 
  : never 

type Lookup<Grd extends Grid, IdCrd = IdCoord> = 
  IdCrd extends `${infer ID}:${infer R extends Index9}${infer G extends Index3}${infer C extends Index3}`
  ? `${ID}:${Grd[R][G][C]}`
  : never

type Solved = `${'R' | 'C' | 'G'}${Index9}:${Digit}`

type SudokuSolved<Grd extends Grid> = Solved extends Lookup<Grd> ? true : false

TypeScript playground

The Diagnose type below shows the exact problems with a solution, rather than just true or false.

type IndexNrs = [1, 2, 3, 4, 5, 6, 7, 8, 9]
type RCGNames = {R: 'row', C: 'column', G: 'group'}

// Evaluates to a union of all missing digits and respective locations.
type Diagnose<Grd extends Grid, Missing = Exclude<Solved, Lookup<Grd>>> =
  [Missing] extends [never]
  ? 'Solution is correct!'
  : Missing extends `${infer RCG extends keyof RCGNames}${infer Ix extends Index9}:${infer D}`
    ? `Missing ${D} in ${RCGNames[RCG]} ${IndexNrs[Ix]}`
    : never

Solution by Oblosys #33407

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

type SudokuSolved<Grid extends number[][][]> =
  | CheckSubGrids<Grid>
  | CheckRows<Tuple2union<Grid>>
  | CheckColumns<Tuple2union<Grid>> extends true
  ? true
  : false

type CheckSubGrids<Grid extends number[][][]> = Grid extends [
  infer Grid1 extends number[][],
  infer Gird2 extends number[][],
  infer Grid3 extends number[][],
  ...infer Rest extends number[][][],
]
  ? CheckSubGrid<Grid1 | Gird2 | Grid3> extends true
    ? CheckSubGrids<Rest>
    : false
  : true

type CheckSubGrid<
  SubGrid extends number[][],
  C extends number = 0 | 1 | 2,
> = C extends C
  ? Digits extends Tuple2union<SubGrid[C]>
    ? true
    : false
  : never

type CheckRows<Rows extends number[][]> = Rows extends Rows
  ? Digits extends Tuple2union<Tuple2union<Rows>>
    ? true
    : false
  : never

type CheckColumns<
  Rows extends number[][],
  I extends number = 0 | 1 | 2,
  J extends number = 0 | 1 | 2,
> = I extends I
  ? J extends J
    ? Digits extends Rows[I][J]
      ? true
      : false
    : never
  : never

type Tuple2union<T extends any[]> = T[number]

Solution by Sun79 #33179

type SudokuSolved<T extends number[][][], D extends Digits = Digits> = [
  | (D extends D ? Digits extends T[Minus1<D>][number][number] ? never : `Unresolved in Row ${D}` : never)
  | (D extends D ? Digits extends T[number][DivBy3<D>][ModBy3<D>] ? never : `Unresolved in Col ${D}` : never)
  | (D extends D ? Digits extends T[DivBy3<D>][ModBy3<D>][number] ? never : `Unresolved in Subgrid ${D}` : never)
] extends [never] ? true : false;

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;
type Sections = [0 | 1 | 2, 3 | 4 | 5, 6 | 7 | 8];
type Minus1<D extends Digits> = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8][D];
type DivBy3<D extends Digits> = Sections[[never, 0, 0, 0, 1, 1, 1, 2, 2, 2][D]];
type ModBy3<D extends Digits> = Sections[[never, 0, 1, 2, 0, 1, 2, 0, 1, 2][D]];

Playground

Explanation

1️⃣ Why Digits extends M[...] Fails Without All Digits

TypeScript evaluates unions like Digits = 1 | 2 | ... | 9 as a whole.

Rule: A union (1 | 2 | ... | 9) can only extend another union if all members are present on the right.
Example:

Digits extends [1, 2, 3, 4, 5, 6, 7, 8, 9][number] // ✅ Passes
Digits extends [1, 2, 3][number]                   // ❌ Fails (missing digits)

If even one digit is missing in the right-hand side, the check fails entirely (❌).

2️⃣ Why D extends D ? ... : never Works

The conditional type D extends D ? ... : never ensures each digit in the union (1 | 2 | ... | 9) is evaluated independently

How it works:
- Without D extends D, TypeScript treats the union as a whole, causing "all-or-nothing” failures.
- With D extends D, TypeScript distributes the union, checking each digit separately.
Example:

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;

// Distributes over each digit:
type Distribute<T> = T extends T ? [T] : never;

Distribute<Digits>
// Resolves to: [1] | [2] | [3] | ... | [9]

This ensures each digit is checked one at a time, avoiding the “all-or-nothing” problem

Solution by teamchong #33129