• 示例工程

type-challenges 仓库中的 Sudoku（31797，hard 难度） 要求你编写一个类型SudokuSolved<T>，在编译期判定一个给定的 9×9 数独盘面是否已经被完整且正确地解开。本文将带你从题目输入结构出发，逐步推导出行、列、宫三条校验线在类型层面的提取与判重方法，最终给出一个可通过仓库全部 8 组测试用例的完整实现，并深入讲解递归条件类型、变长元组、矩阵转置等核心技巧。

一、题目概览：挑战背景与输入表示

题目由 Bruno Ladeia 提出（见 info.yml 的元数据），标注难度为hard，标签为union / array / tuple / game。README 中明确说明，该题改编自 Advent of TypeScript 2023 的第 22 天挑战（由 TypeHero 设计），原题灵感来自经典的数独游戏规则。

题目要求一句话概括就是：编写一个类型，验证一个数独游戏已被解出。

在动手前，先看题目的起点模板 template.ts：

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

模板只提供了两个东西：

• Digits：1～9 的字面量联合类型，提示盘面单元格的合法取值；
• SudokuSolved：等待你实现的空壳（当前为any）。

输入结构由 test-cases.ts 中的测试数据决定：一个数独盘面被编码为9 行 × 3 个宫 × 3 个格子的三层嵌套元组。以第一个测试用例为例：

type test_sudoku_1_actual = SudokuSolved<[ [[1, 2, 3], [5, 6, 7], [4, 8, 9]], // 第 1 行（3 个 3×3 宫） [[4, 8, 9], [1, 2, 3], [5, 6, 7]], [[5, 6, 7], [4, 8, 9], [1, 2, 3]], ... ]>

也就是说，泛型参数T的类型形状是number[][][]：T[行索引][宫索引][格索引]。9 行 × 3 宫 × 3 格恰好组成一个 9×9 的完整盘面，且盘面中没有空格——"已解出"意味着每一个格子都已填入数字 1～9，且满足数独规则。

二、判定规则：行、列、宫三条"线"都必须无重复

数独的规则可以抽象为：9 条横线（行）、9 条竖线（列）、9 个 3×3 方块（宫）中的每一条，都必须恰好包含数字 1～9 各一次。

由于题目保证盘面完整（无空位），"恰好包含 1～9 各一次"等价于更易实现的条件——一条线上 9 个数字两两不重复：

• 若一条线上存在重复数字，则必然缺少某个 1～9 中的数字 → 非法；
• 若一条线上 9 个数字互不重复，且每个格子取值来自 1～9，则恰好覆盖 1～9 → 合法。

因此，整个解题的核心可以拆成三个子问题：

1. 如何把"一条线"表示成一个 9 元组；
2. 如何从嵌套结构T中抽出行、列、宫三类线；
3. 如何判定一个元组内没有重复元素。

三、测试用例分析：8 组用例在考什么

test-cases.ts 末尾（第 99～108 行）定义了最终的断言：

type cases = [ Expect<Equal<test_sudoku_1_actual, true>>, Expect<Equal<test_sudoku_2_actual, true>>, Expect<Equal<test_sudoku_3_actual, true>>, Expect<Equal<test_sudoku_4_actual, false>>, Expect<Equal<test_sudoku_5_actual, false>>, Expect<Equal<test_sudoku_6_actual, false>>, Expect<Equal<test_sudoku_7_actual, false>>, Expect<Equal<test_sudoku_8_actual, false>>, ]

其中Expect与Equal来自仓库的测试工具包 utils/index.d.ts，Expect<T extends true>只有在传入true时才通过编译。前 3 组是合法已解盘面，应返回true；后 5 组各有破绽，应返回false。逐一核对可以看清每个破绽命中的校验维度：

值得注意的是：第 4～6 组都在行维度上埋雷，第 7 组在宫维度，第 8 组在列维度——它们共同提醒我们，三类线一条都不能漏检。

四、从零搭建解决方案

下面按"先搭通用零件、再组装主类型"的顺序，逐步构造一个可运行、可通过全部用例的实现。

第 1 步：通用零件——元组判重

判定"一条线无重复"，用递归条件类型遍历元组，把见过的元素累积进Seen，一旦当前元素已在Seen中出现即返回true：

type HasDuplicate<T extends unknown[], Seen extends unknown[] = []> = T extends [infer F, ...infer R] ? F extends Seen[number] ? true : HasDuplicate<R, [...Seen, F]> : false type IsValidLine<L extends unknown[]> = HasDuplicate<L> extends true ? false : true

这里用到了两条关键机制：

• 递归条件类型 + 变长元组：[infer F, ...infer R]每次拆出首元素F与剩余元组R，[...Seen, F]累积已见元素；
• Seen[number]索引访问：将元组的所有元素合并成联合类型，F extends Seen[number]即"F 是否在已见集合中"。

需要留意一个细节：该判重逻辑成立的前提是每个格子都是字面量数字类型。若盘面中出现宽泛的number，number extends 1 | 2 | …会判定为 false，判重会失效——这也是题目刻意用字面量元组作为测试输入的原因。

第 2 步：提取"行"——展平 3 宫

一行由 3 个宫组成，展平后即 9 个数字：

type FlattenRow<Row extends unknown[][], Acc extends unknown[] = []> = Row extends [infer F extends unknown[], ...infer R extends unknown[][]] ? FlattenRow<R, [...Acc, ...F]> : Acc

再把 9 行整体映射一遍，得到"展平后的 9×9 矩阵"：

type MapRows<T extends unknown[][][], Acc extends unknown[][] = []> = T extends [infer F extends unknown[][], ...infer R extends unknown[][][]] ? MapRows<R, [...Acc, FlattenRow<F>]> : Acc

第 3 步：提取"列"——矩阵转置

列比行麻烦：需要从每一行中取相同下标的元素组成新元组。一个优雅的做法是矩阵转置：把 9×9 矩阵转置后，"列"就变成了"行"，可以直接复用第 2 步的行校验。

转置的递归思路是：反复剥离每一行的首元素，把它们收集成新的行：

type Transpose<M extends unknown[][], Acc extends unknown[][] = []> = M extends [infer F extends unknown[], ...infer R extends unknown[][]] ? F extends [infer H, ...infer T] ? Transpose<[...R, T], [...Acc, [H]]> : never : Acc

追踪一次小例子：[[1,2,3],[4,5,6],[7,8,9]]经过三轮迭代后，Acc依次收集[1]、[4]、[7]……最终得到[[1],[4],[7],[2],[5],[8],[3],[6],[9]]，正是转置矩阵。它的本质是"首列逐行出队 → 其余行队尾入队"，循环往复直到所有元素被重新排列。

第 4 步：提取"宫"——每三行取三个竖直宫

宫是 3×3 方块：以三行（如第 0～2 行）为一组，把它们在同一列位置上的 3 个宫首尾拼接，即可得到该组的 3 条宫线：

type GetBoxes<T extends unknown[][][], Acc extends unknown[][] = []> = T extends [ infer A extends unknown[][], infer B extends unknown[][], infer C extends unknown[][], ...infer R extends unknown[][][], ] ? GetBoxes< R, [ ...Acc, [...A[0], ...B[0], ...C[0]], [...A[1], ...B[1], ...C[1]], [...A[2], ...B[2], ...C[2]], ] > : Acc

每轮吞掉 3 行，产出 3 条 9 元素宫线（分别是该三行中第 0、1、2 列位置的竖直宫）。3 轮迭代后正好得到全部 9 个宫。

第 5 步：组装主类型

最后写一个"逐条线校验"的驱动器，并串联行、列、宫三类校验：

type AllValid<Lines extends unknown[][], Acc extends boolean = true> = Lines extends [infer F extends unknown[], ...infer R extends unknown[][]] ? AllValid<R, Acc extends true ? IsValidLine<F> : false> : Acc type SudokuSolved<T extends unknown[][][]> = AllValid<MapRows<T>> extends true ? AllValid<Transpose<MapRows<T>>> extends true ? AllValid<GetBoxes<T>> extends true ? true : false : false : false

AllValid用一个累积的boolean实现短路：一旦某条线非法，后续迭代直接返回false，避免无谓的深度递归。整个SudokuSolved按"行 → 列 → 宫"三级嵌套展开，任一环节非法即整体为false。

五、完整实现与验证

将上述零件合并，就是一份可直接放进 template.ts 的完整答案：

type Digits = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 type HasDuplicate<T extends unknown[], Seen extends unknown[] = []> = T extends [infer F, ...infer R] ? F extends Seen[number] ? true : HasDuplicate<R, [...Seen, F]> : false type IsValidLine<L extends unknown[]> = HasDuplicate<L> extends true ? false : true type FlattenRow<Row extends unknown[][], Acc extends unknown[] = []> = Row extends [infer F extends unknown[], ...infer R extends unknown[][]] ? FlattenRow<R, [...Acc, ...F]> : Acc type MapRows<T extends unknown[][][], Acc extends unknown[][] = []> = T extends [infer F extends unknown[][], ...infer R extends unknown[][][]] ? MapRows<R, [...Acc, FlattenRow<F>]> : Acc type Transpose<M extends unknown[][], Acc extends unknown[][] = []> = M extends [infer F extends unknown[], ...infer R extends unknown[][]] ? F extends [infer H, ...infer T] ? Transpose<[...R, T], [...Acc, [H]]> : never : Acc type GetBoxes<T extends unknown[][][], Acc extends unknown[][] = []> = T extends [ infer A extends unknown[][], infer B extends unknown[][], infer C extends unknown[][], ...infer R extends unknown[][][], ] ? GetBoxes< R, [ ...Acc, [...A[0], ...B[0], ...C[0]], [...A[1], ...B[1], ...C[1]], [...A[2], ...B[2], ...C[2]], ] > : Acc type AllValid<Lines extends unknown[][], Acc extends boolean = true> = Lines extends [infer F extends unknown[], ...infer R extends unknown[][]] ? AllValid<R, Acc extends true ? IsValidLine<F> : false> : Acc type SudokuSolved<T extends unknown[][][]> = AllValid<MapRows<T>> extends true ? AllValid<Transpose<MapRows<T>>> extends true ? AllValid<GetBoxes<T>> extends true ? true : false : false : false

对照 test-cases.ts 中的 8 组用例逐一推演：

• test_1～3：行、列、宫 27 条线均无重复 →true；
• test_4～6：各自某行存在重复数字（4、2、1），AllValid<MapRows<T>>短路为false→false；
• test_7：左上宫[1,2,3,2,3,5,3,5,6]重复，宫校验拦截 →false；
• test_8：行全相同，转置后每列 9 个相同数字，列校验拦截 →false。

六、如何在本地运行与验证

本仓库的每个挑战都由四个文件构成，Sudoku 也不例外：

• README.md：题目描述；
• template.ts：需要填写的类型骨架；
• test-cases.ts：判定用的测试用例；
• info.yml：难度、标签、作者等元数据。

按仓库根目录 README.md 的说明，你可以在本地复现整个做题流程：克隆仓库后执行pnpm install安装依赖，再执行pnpm generate（或带--keep-changes/-K参数保留你的修改并同步更新）生成可在本地 IDE 中打开的 playground。将上面的完整实现写入template.ts，用 TypeScript 编译器以严格模式检查test-cases.ts，只要cases数组中的 8 组Expect<Equal<...>>全部通过编译，即证明实现正确。

七、技术要点回顾与延伸

这道 hard 题综合了类型层面多个高频技巧，值得逐条沉淀：

1. 递归条件类型是类型级编程的循环：几乎所有结构化遍历（判重、展平、映射、转置）都依赖[infer F, ...infer R]的拆解-递归模式；
2. 变长元组（variadic tuple）用于"携带状态"：[...Seen, F]、[...Acc, ...F]让每次递归都能携带已计算的结果，实现累加器式的函数式写法；
3. 索引访问Seen[number]将元组折叠为联合类型：配合extends即可实现成员判定，这是判重类题目的标准套路；
4. 矩阵转置的思路可以复用：把"取列"转化为"取行"，大幅降低实现复杂度；该技巧同样出现在本仓库的 25270-medium-transpose 等题目中；
5. 短路累积布尔值控制递归深度：一旦发现非法线立刻收敛为false，是控制类型实例化开销的实用手法。

如果你还想在数独主题上继续精进，仓库中还有一道同属#game标签的姊妹题 35314-hard-valid-sudoku（校验一个含空格盘面是否"有效"而非"已解出"），两者的校验维度（行/列/宫）一致，但输入允许0占位，边界处理值得对比体会。

总而言之，SudokuSolved是一次把"领域规则翻译成类型约束"的绝佳练习：它证明 TypeScript 类型系统不仅能描述数据形状，还能在编译期执行真实的业务校验逻辑——这也正是 type-challenges 项目希望通过一个个挑战帮你建立的类型直觉。

• 示例工程