freeCodeCamp 每日编程挑战 279：使用回溯法求解最长多米诺骨牌链（Longest Domino Chain）

freeCodeCamp 每日编程挑战 279：使用回溯法求解最长多米诺骨牌链（Longest Domino Chain）

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp

本篇技术指南围绕 freeCodeCamp 课程仓库中「每日编程挑战（Daily Coding Challenges）」模块的第 279 号挑战展开：给定一组由 0–6 数字对构成的多米诺骨牌，要求找出其中最长的合法链条，并允许任意翻转骨牌。读完本文你将掌握该挑战的完整规则、官方示例解法中的递归回溯实现细节、测试断言设计思路，以及它在前端练习与后端每日挑战接口中的落地方式，可以直接在本地练习并验证你的实现。

挑战背景：Daily Coding Challenges 在 freeCodeCamp 中的位置

「每日编程挑战」是 freeCodeCamp 课程体系中一个独立的 JavaScript 挑战块（block），在仓库中由curriculum/structure/blocks/daily-coding-challenges-javascript.json定义。该块以isUpcomingChange: true标记为进行中的新内容，包含从Challenge 1: Vowel Balance到Challenge 365: The Last Challenge: Bucket Fill 3共 365 道挑战，每道挑战对应一年中的一天。Challenge 279 位于列表第 1122–1124 行，紧随其后的 280 是「Mongo ID Date」，前一道 278 是「Coffee Order Parser」。

这些挑战遵循统一的 Markdown 文件结构，每个文件包含 frontmatter（id、title、challengeType、dashedName）、--description--题目描述、--hints--测试断言、--seed--起始代码和--solutions--参考答案。Challenge 279 的challengeType: 28属于编码挑战类型，前端由client/src/components/daily-coding-challenge/下的widget.tsx、calendar.tsx等组件渲染，后端则由api/src/daily-coding-challenge/模块按日期提供每日题目数据。

题目规则详解

curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69f35a5bb823ed620fcb7cb8.md给出了getLongestChain(dominoes)函数的要求：输入一个二维数组，代表一组多米诺骨牌，返回最长的合法链。具体规则如下：

• 骨牌表示：每张骨牌是一对 0–6 之间的数字，例如[3, 2]；
• 链的合法性：后一张骨牌的第一个数字必须与前一张骨牌的第二个数字相等，即chain[i][1] === chain[i+1][0]；
• 两端自由：第一张骨牌的第一个数字、最后一张骨牌的第二个数字不需要与任何东西匹配；
• 允许翻转：任何骨牌都可以翻转，[3, 2]既可以按[3, 2]打，也可以按[2, 3]打；
• 解的唯一性：题目保证恰好存在一条最长合法链（长度上唯一，但翻转/顺序可能不唯一，见下文测试设计）。

示例：给定[[1, 2], [4, 5], [2, 3]]，最长链为[[1, 2], [2, 3]]，因为[4, 5]两端分别与1、2、3都不衔接。

测试断言设计：为何答案允许两种表示

该挑战的--hints--部分共有 5 组测试，全部通过 Chai 的assert.isTrue断言链的 JSON 序列化结果等于result1或result2中的任意一个。这种「二选一」的设计源于骨牌翻转带来的等价性：整条链从头到尾全部翻转后依然是一条合法的等长链。

以第二组测试为例，输入[[2, 1], [4, 3], [5, 3]]要求返回[[4, 3], [3, 5]]或[[5, 3], [3, 4]]——后者正是前者整体翻转的结果。测试代码片段如下：

const chain = JSON.stringify(getLongestChain([[2, 1], [4, 3], [5, 3]])); const result1 = JSON.stringify([[4, 3], [3, 5]]); const result2 = JSON.stringify([[5, 3], [3, 4]]); assert.isTrue(chain === result1 || chain === result2);

5 组测试的输入规模由简到繁，覆盖了不同复杂度：

注意第 4、5 组测试中，输入里都混入了无法接入最长链的「干扰骨牌」（如[0,3]、[2,3]、[1,2]等），这要求算法必须遍历所有可能的组合才能保证结果是全局最优，而不是简单的贪心拼接。此外第 4 组测试验证了双点骨牌（[6,6]、[1,1]）的正确处理——它们翻转前后完全相同，a !== b的判断保证了不会产生重复分支。

种子代码：起点与目标

挑战提供的起始代码（--seed--）非常精简，只给出了函数骨架，要求补全实现逻辑：

function getLongestChain(dominoes) { return dominoes; }

--seed-contents--只保留函数签名和直接返回入参的占位行为，挑战者需要自行实现搜索逻辑。这种「空壳函数 + 测试驱动」的模式贯穿整个 daily-coding-challenges 块，评价体系依赖--hints--中独立的assert断言（本挑战的断言使用assert.isTrue比较序列化字符串），而非固定的输入输出对，因此实现方案可以自由选择，只要最终返回的链在语义上等价即可。

官方解法逐行拆解：递归回溯（Backtracking）

--solutions--中给出了完整参考实现，其核心是递归回溯：尝试所有可能的起始骨牌，从当前链的末端数字出发，逐一尝试剩余的每一张骨牌（包括翻转），递归地扩展链条，并始终保留长度最长的结果。

内部递归函数search

function search(chain, remaining) { let best = chain; const last = chain[chain.length - 1][1]; for (let i = 0; i < remaining.length; i++) { const [a, b] = remaining[i]; const rest = remaining.filter((_, j) => j !== i); if (a === last) { const result = search([...chain, [a, b]], rest); if (result.length > best.length) best = result; } if (b === last && a !== b) { const result = search([...chain, [b, a]], rest); if (result.length > best.length) best = result; } } return best; }

关键设计点：

• best初始化为当前chain：当没有剩余骨牌可接时（remaining为空或全部不匹配），search直接返回当前链，这构成了递归的终止条件；同时best始终保留「不追加任何骨牌」作为兜底，保证任何状态下都有合法返回。
• last取自链尾的第二数字：chain[chain.length - 1][1]是需要被下一张骨牌匹配的接口值。
• 剩余骨牌筛选：remaining.filter((_, j) => j !== i)构造出移除第i张后的新剩余集合，配合[...chain, [a, b]]的不可变风格（每次递归产生新数组），天然避免了对原数组的原地修改和回溯时需要撤销状态的问题。
• 方向判断：a === last时按原方向[a, b]接入；b === last && a !== b时按翻转方向[b, a]接入。a !== b的条件是性能与正确性的关键优化——对于双点骨牌（如[6,6]），翻转后与原来完全相同，若不排除会生成重复分支、浪费指数级搜索空间，甚至导致某些场景下出现「自我重复扩展」的死循环式无效分支。
• 不可变展开 + 长度比较：result.length > best.length确保每个分支返回的都是该分支下的局部最优，逐层向上比较后，search最终返回从当前chain出发能扩展出的最长链。

外层主函数：枚举所有起点

let best = []; for (let i = 0; i < dominoes.length; i++) { const [a, b] = dominoes[i]; const rest = dominoes.filter((_, j) => j !== i); const r1 = search([[a, b]], rest); if (r1.length > best.length) best = r1; if (a !== b) { const r2 = search([[b, a]], rest); if (r2.length > best.length) best = r2; } } return best;

主函数对每一张骨牌分别以其原始方向和翻转方向作为链的起点进行搜索，best初始化为空数组[]，与所有递归结果比较后返回全局最长链。best.length的比较天然处理了「长度相同取谁」的问题——由于题目保证恰好存在一条长度唯一的最长链，任何一条等长的合法链都会被测试接受。

复杂度分析

从实现结构看，该算法的时间复杂度为指数级：对n张骨牌，每个递归层都在remaining上做线性filter，最坏情况下的搜索空间接近O(n!)（排列数级），空间复杂度为O(n)（递归深度与每层新数组）。因此本解法适合n较小（挑战用例最大为 9 张骨牌）的输入规模，属于「正确性优先于效率」的教学式实现——这正是理解回溯、子集枚举与状态不可变性的理想载体。

与 Challenge 214「Domino Chain Validator」的关系：验证 vs 求解

同一课程块中，Challenge 214（curriculum/challenges/english/blocks/daily-coding-challenges-javascript/699c8e045ee7cb94ed2322d5.md）是一道难度递进的姊妹题：它只要求判断一个给定的骨牌序列是否构成合法链（输入数组已经排好顺序，不允许重排或翻转），解法是一个O(n)的线性扫描：

function isValidDominoChain(dominoes) { for (let i = 0; i < dominoes.length - 1; i++) { if (dominoes[i][1] !== dominoes[i+1][0]) return false } return true; }

两者的对比清晰地展示了「验证」与「求解」两类问题的本质差异：Challenge 214 是确定性的顺序检查，而 Challenge 279 需要在「任意排列 + 任意翻转」的解空间中搜索全局最优，复杂度从线性跃升到指数级。两题共享challengeType: 28与相同的 Markdown 结构规范，适合放在一起练习，形成从基础到进阶的完整理解闭环。

在课程生态中的实际落地

前端渲染与交互

这类挑战在前端由client/src/components/daily-coding-challenge/目录承载，widget.tsx负责展示每日挑战卡片（题目、测试、编辑器），calendar.tsx与calendar-day.tsx提供按日期浏览挑战的日历视图。client/src/utils/daily-coding-challenge-validator.ts定义了挑战数据从数据库到前端的形状校验规则：每条挑战包含id、challengeNumber、title、date、description，以及javascript与python两个语言版本的数据块，每个语言块由tests（text+testString数组）和challengeFiles（fileKey+contents数组）构成——其中testString就是本文开头那些assert断言脚本，challengeFiles则是--seed--的起始代码。该校验器基于 Joi 实现，并对challengeNumber要求为不小于 1 的整数。

后端数据接口

api/src/daily-coding-challenge/routes/daily-coding-challenge.ts提供了 6 个公开 GET 接口，将挑战数据按日期提供给前端：

• GET /daily-coding-challenge/date/:date——按YYYY-MM-DD精确查询单日挑战，日期格式非法返回 400，早于今天 US Central 时间之前不存在返回 404；
• GET /daily-coding-challenge/day/:day——按MM-DD查询（会换算到对应的年份）；
• GET /daily-coding-challenge/today——返回当日挑战；
• GET /daily-coding-challenge/month/:month——按YYYY-MM返回整月挑战摘要（仅id、challengeNumber、date、title）；
• GET /daily-coding-challenge/all——返回全部已发布挑战摘要；
• GET /daily-coding-challenge/newest——返回最新挑战的日期。

数据通过 Prisma 从dailyCodingChallenges表中读取，接口代码中注释明确指出挑战数据仅发布到 2026 年 8 月 10 日为止；挑战提交仍走主 API 的挑战完成路由（api/src/daily-coding-challenge/README.md亦说明「每日挑战提交仍位于主 API 部分」）。所有请求都会通过fastify.Sentry记录dcc.challenge_viewed、dcc.challenge_not_found等指标，便于观测每日挑战的访问量。

本地练习与验证建议

想要动手验证你的getLongestChain实现，可以按以下步骤：

1. 打开curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69f35a5bb823ed620fcb7cb8.md，将--seed--的函数骨架复制到你的编辑器；
2. 用--hints--中的 5 组测试逐一断言你的输出（注意JSON.stringify后与result1/result2任一等价即通过）；
3. 与--solutions--的参考实现对照，重点体会「双点骨牌去重」「剩余集合不可变筛选」「best兜底」三个设计点；
4. 如果想验证自己的理解，可先完成 Challenge 214 的线性验证版本，再升级到本挑战的搜索版本，感受问题复杂度随约束放宽而爆炸式增长的过程。

小结

Challenge 279 是一个教科书式的递归回溯题：规则简单（数字匹配 + 允许翻转），但解空间巨大（排列 × 2 的翻转组合），迫使你跳出贪心思维、建立完整的搜索树心智模型。官方解法以不可变数组 + 递归 + 长度比较三个元素，在 20 行代码内优雅地解决了问题，是学习回溯算法、剪枝思想与「验证 vs 求解」问题区分度的优质素材。配合本仓库中该挑战的前端渲染组件与后端数据接口，你可以完整体验一道 freeCodeCamp 每日编程挑战从题目、测试、求解到上线的全链路。

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp