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
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
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 Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
type DigitsX3<D = Digits> = [D, D, D]
type Grid<Row = DigitsX3<DigitsX3>> = [Row, Row, Row, Row, Row, Row, Row, Row, Row]
type SudokuSolved<T extends Grid> = [
ReturnType<<D extends Digits>() => D extends D ? Digits extends RowValues<T, D> ? never : `Unresolved in Row ${D}` : D> |
ReturnType<<D extends Digits>() => D extends D ? Digits extends ColValues<T, D> ? never : `Unresolved in Col ${D}` : D> |
ReturnType<<D extends Digits>() => D extends D ? Digits extends SubgridValues<T, D> ? never : `Unresolved in Subgrid ${D}` : D>
] extends [never] ? true : false
type RowValues<G extends Grid, Row extends Digits> = G[Row][any][any]
type ColValues<G extends Grid, Col extends Digits> = G[any][[any, 0, 0, 0, 1, 1, 1, 2, 2, 2][Col]][[any, 0, 1, 2, 0, 1, 2, 0, 1, 2][Col]]
type SubgridValues<G extends Grid, Subgrid extends Digits>
= G[[0 | 1 | 2, 3 | 4 | 5, 6 | 7 | 8][[any, 0, 0, 0, 1, 1, 1, 2, 2, 2][Subgrid]]][[any, 0, 1, 2, 0, 1, 2, 0, 1, 2][Subgrid]][any]
Solution by teamchong #33129