提到“P674 三羊献瑞”刷过蓝桥杯省赛或者练过 DFS 回溯题单的朋友应该都对这个名字有印象。题目不长看起来就是一个汉字竖式谜祥 瑞 生 辉 三 羊 献 瑞 --------------- 三 羊 生 瑞 气已知每个汉字代表一个 0 到 9 的数字不同汉字代表不同数字并且“祥”和“三”不能是 0。要求的就是“三羊献瑞”这个四位数到底是多少。这题是典型的“把加法竖式换成字母/汉字”的密码算式题英文里叫 cryptarithm 或者 alphametic国内更喜欢叫竖式谜。它既有数学推理的味道又非常适合拿来练搜索和回溯变量不多不少直接暴力也能跑但配合进位分析可以手算出答案。这篇文章我会把 P674 这题的完整解法拆开讲。先带你人工推理一遍再给 C 和 Python 两种可提交的 DFS 实现最后把我在刷题过程中遇到的坑和验证技巧一次性说清楚。不管你是刚入门 OJ 的新手还是准备蓝桥杯、ACM 的选手这篇都能给你一点能直接抄作业的东西。1. 题目到底在做什么拆开竖式谜的核心约束很多第一次接触“三羊献瑞”的人第一反应是这不就是个小学数学题吗确实是但它作为编程题出现时核心并不是让你在纸上试数字而是让你把“枚举 约束满足”这件事用代码表达出来。1.1 把汉字映射成变量先把竖式里的每个汉字都换成字母方便后面推导和写代码汉字变量说明祥A四位数“祥瑞生辉”的千位不能为 0瑞B两个加数都出现且都出现在个位/千位等处生C出现在第一个加数的十位也出现在结果的百位辉D只出现在第一个加数的个位三E结果“三羊生瑞气”的万位不能为 0羊F结果的千位两个加数的千位则不是它献G第二个加数的十位气H结果的个位于是竖式可以写成A B C D E F G B ---------- E F C B H这个“字母化”的过程非常关键。因为题目里汉字重复出现比如“瑞”在加数和结果里都有如果你直接在代码里用一堆if去判断字符串会非常别扭。改成变量之后约束就变得很清晰A和E不能等于 08 个变量必须两两不同等式ABCD EFGB EFCBH必须成立。1.2 为什么这道题适合用来练 DFS先算一笔暴力账。8 个汉字要从 10 个数字里选每个汉字不同那就是排列数10P8 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 1814400一百八十万种情况。对 C 来说这个量级随便跑对 Python 来说itertools.permutations全排一遍也就一两秒的事。所以这题哪怕不用任何优化暴力枚举都能过。但题目如果只考暴力那就太没意思了。它被经常选进 OJ 和蓝桥杯练习是因为它包含了一个搜索题最基本的几个要素状态定义当前枚举到第几个汉字可选值集合0-9 中没用过的数字剪枝条件祥、三不能为 0终态判断把 8 个数字代回竖式看等式是否成立。这几乎是 DFS 回溯的教科书模板。你把这题吃透后面遇到“八皇后”“全排列”“数独”等一堆搜索题套路都是一样的。2. 先手工推理一波进位分析能直接锁定答案不要急着敲代码。竖式谜的魅力在于很多约束可以从“进位”里白嫖。P674 这题尤其典型最高位的进位直接告诉你“三 1”。2.1 最高位结果多出一位说明千位一定进位两个四位数相加结果却是五位数“三羊生瑞气”。五位数的最高位只能来自千位相加后的进位所以万位只能是 1。也就是说三 1这是全题最强的一个条件也是很多人第一次看这道题时最容易忽略的地方。你如果直接写程序枚举不太会在意这件事但手推时“三 1”能省掉大量分支。接着看千位祥 三 百位进位 羊 10因为千位向万位进了一位所以右边必须加10。已知“三 1”假设百位进位是c3只有 0 或 1那么祥 1 c3 羊 10变形一下羊 祥 - 9 c3由于“羊”是数字 0 到 9这就把“祥”的范围卡死了。如果c3 0则羊 祥 - 9只能是祥 9羊 0如果c3 1则羊 祥 - 8可能是祥 8羊 0也可能是祥 9羊 1。但“羊 1”会和“三 1”重复排除。所以只剩两个候选候选1祥 9羊 0百位进位 c3 0 候选2祥 8羊 0百位进位 c3 1候选 2 能不能成立还要看百位那一列。百位是瑞 羊 十位进位 生 10 × c3如果羊 0c3 1那么瑞 十位进位 生 10由于“瑞”最大是 9“十位进位”最大是 1左边最多是 10。要让右边等于“生 10”只能是生 0。但“羊”已经是 0数字重复所以候选 2 无解。于是唯一可能是祥 9羊 0百位进位 c3 02.2 顺着进位一步步推下去百位进位已经确定为 0再看百位这一列瑞 羊 十位进位 生羊 0所以生 瑞 十位进位因为“生”和“瑞”不能相同所以十位进位不能是 0只能是 1生 瑞 1接下来看十位生 献 个位进位 瑞 10 × 十位进位把“生 瑞 1”和“十位进位 1”代进去(瑞 1) 献 个位进位 瑞 10两边都消掉“瑞”献 个位进位 9个位进位只能是 0 或 1。如果个位进位是 0那么“献 9”但“祥”已经等于 9重复了所以个位进位只能是 1得到献 8最后看个位辉 瑞 气 10 × 个位进位也就是说辉 瑞 气 10现在已知的已经很多了三 1 羊 0 献 8 祥 9“生 瑞 1”所以从剩下没被占用的数字里挑“瑞”和“生”瑞 2生 3剩下 4、5、6、7 给辉和气需要满足“辉 2 气 10”不可能瑞 3生 4剩下 2、5、6、7需要“辉 3 气 10”试不出瑞 4生 5剩下 2、3、6、7需要“辉 4 气 10”试不出瑞 5生 6剩下 2、3、4、7需要“辉 5 气 10”取辉 7气 2 正好成立瑞 6生 7剩下 2、3、4、5需要“辉 6 气 10”给不出整数解。所以唯一解是祥 9 瑞 5 生 6 辉 7 三 1 羊 0 献 8 气 2代回竖式9 5 6 7 1 0 8 5 --------- 1 0 6 5 2也就是三羊献瑞 10852.3 为什么还要写程序看到这里可能有同学会问手推都能推出来为啥还要写程序这就要看你刷题的目的是什么了。手推适合理解进位逻辑也确实能体现这道题的“巧”但 OJ 判题要的是稳定可复现的解法。如果题目把汉字换掉、把竖式加长甚至改成“SEND MORE MONEY”这种经典英文谜题你再靠手推就非常累。写一个通用 DFS 搜索换个等式就能跑这才是编程题该有的样子。3. 代码实现DFS 回溯的完整套路手推版适合发朋友圈装酷提交版还是得靠搜索。这题我用 C 和 Python 各写了一个版本思路一致你挑自己熟悉的看。3.1 用数组下标代替汉字变量代码里我用一个长度为 8 的数组存数字// index: 0祥 1瑞 2生 3辉 4三 5羊 6献 7气 int a[8]; bool used[10];DFS 从dfs(0)开始每次给第step个汉字选一个数字。关键点有两个选过的数字不能再选用used数组记录一旦给“祥”或“三”赋 0直接跳过。当 8 个变量都填完就把它们拼成整数检查加法是否成立。3.2 C 完整代码#include iostream using namespace std; int a[8]; // 0祥 1瑞 2生 3辉 4三 5羊 6献 7气 bool used[10]; void dfs(int step) { if (step 8) { int 祥 a[0]; int 瑞 a[1]; int 生 a[2]; int 辉 a[3]; int 三 a[4]; int 羊 a[5]; int 献 a[6]; int 气 a[7]; // 高位的字不能是 0其实 dfs 里已经过滤这里再写一遍更稳 if (祥 0 || 三 0) return; int left1 祥 * 1000 瑞 * 100 生 * 10 辉; // 祥瑞生辉 int left2 三 * 1000 羊 * 100 献 * 10 瑞; // 三羊献瑞 int right 三 * 10000 羊 * 1000 生 * 100 瑞 * 10 气; // 三羊生瑞气 if (left1 left2 right) { cout 三羊献瑞 三 羊 献 瑞 endl; cout 祥 瑞 生 辉 三 羊 献 瑞 三 羊 生 瑞 气 endl; } return; } for (int d 0; d 9; d) { if (used[d]) continue; // 祥step0和三step4都不能是 0 if (d 0 (step 0 || step 4)) continue; used[d] true; a[step] d; dfs(step 1); used[d] false; } } int main() { dfs(0); return 0; }这段代码在我的机器上运行几乎是瞬间出结果。输出三羊献瑞 1085 9567 1085 10652注意used数组的回溯赋值是 DFS 最容易写错的地方。dfs递归完成后一定要把used[d]恢复成false否则下一次循环会漏掉大量排列。3.3 Python 版本代码量更少如果你在蓝桥杯练习系统里用 Python 提交建议直接上itertools.permutationsfrom itertools import permutations for p in permutations(range(10), 8): 祥, 瑞, 生, 辉, 三, 羊, 献, 气 p if 祥 0 or 三 0: continue left1 祥 * 1000 瑞 * 100 生 * 10 辉 left2 三 * 1000 羊 * 100 献 * 10 瑞 right 三 * 10000 羊 * 1000 生 * 100 瑞 * 10 气 if left1 left2 right: print(f三羊献瑞 {三}{羊}{献}{瑞}) print(f{祥}{瑞}{生}{辉} {三}{羊}{献}{瑞} {三}{羊}{生}{瑞}{气})permutations(range(10), 8)生成的正好是 10 个数字中挑 8 个的所有排列天然满足“不同汉字不同数字”。Python 跑完整轮大概一两秒对这类小规模搜索完全够用。3.4 进阶按列带进位校验直接拼整数判断虽然简单但有一个小缺点它必须等 8 个数字全部确定后才能判断。如果竖式很长、变量很多比如经典题SEND MORE MONEY全排列数量会爆炸最好一边填数字一边用“逐列 进位”剪枝。逐列校验的思想很直观。从个位开始每一列满足(前一个进位 本列上方所有数字) % 10 本列结果位数字 (前一个进位 本列上方所有数字) / 10 下一个进位对这道题来说逐列校验可以写成类似// 假设已经得到 祥、瑞、生、辉、三、羊、献、气 // c1 是个位进位c2 是十位进位c3 是百位进位 int c1 (辉 瑞) / 10; if ((辉 瑞) % 10 ! 气) return; int c2 (生 献 c1) / 10; if ((生 献 c1) % 10 ! 瑞) return; int c3 (瑞 羊 c2) / 10; if ((瑞 羊 c2) % 10 ! 生) return; int c4 (祥 三 c3) / 10; if ((祥 三 c3) % 10 ! 羊) return; if (c4 ! 三) return;这个版本更贴近竖式本身也能在填完一部分变量后提早判断。不过 P674 这题变量只有 8 个直接全排列已经很快我用逐列校验更多是出于“理解进位”的目的。两种判断方式的取舍如下方式优点缺点适合场景直接拼整数代码短不容易写错需要所有变量确定后才能判断变量少、等式固定逐列带进位可以配合搜索进行剪枝代码长要仔细定义每列进位变量多、竖式长、需要剪枝4. 实战排雷这题常见的坑和调试技巧这道题看起来简单但我在一些交流群里见过不少人卡住甚至提交几次都 WA。下面这些坑基本覆盖了大部分“看起来没问题但就是不对”的案例。4.1 高频错误清单错误类型具体表现解决方法漏掉“不同汉字不同数字”直接用 8 层 for 循环可能出现同一个数字被多个汉字占用用used数组或permutations最高位允许为 0“三”或“祥”被赋成 0程序仍继续计算在赋值或最终判断里排除 0结果位数写错把“三羊生瑞气”当成四位数三 * 1000 ...确认结果是五位数万位是“三”汉字映射错位“生”在加数和结果里位置弄混先把竖式抄成变量等式再写代码回溯忘记恢复状态used[d]一直是 true导致漏解递归返回后used[d] false忽略进位手推和逐列校验时没考虑上一位的进位每一列都要加前一个进位4.2 怎么确认答案是对的输出 1085 之后别急着交。把公式代回去验证一遍9567 1085 ------ 10652再看汉字对应关系祥 9 瑞 5 生 6 辉 7 三 1 羊 0 献 8 气 2代入竖式9 5 6 7 1 0 8 5 --------- 1 0 6 5 2完全吻合。在 OJ 上如果题目只要求输出“三羊献瑞”这个数那就直接输出1085。有的版本会让写完整竖式那就把三行一起打印出来。4.3 一个很实用的小技巧如果你调试时发现结果不止一个大概率是两种原因一是允许了最高位为 0二是没检查“不同汉字不同数字”。这两个约束只要漏一个解会瞬间变多。另外不要在最后判断时才去排除最高位为 0。更好的做法是在 DFS 赋值的瞬间就剪掉if (d 0 (step 0 || step 4)) continue;这样能少生成大量无效排列。虽然这题规模小剪不剪都能过但养成“尽早剪枝”的习惯对后面更复杂的搜索题帮助很大。4.4 如果题目给你的是别的汉字竖式很多 OJ 会把“三羊献瑞”改头换面比如换成“春风吹满楼”之类的喜庆词结构完全一样。你只要记住通用思路把竖式里的不同汉字编号用 DFS 枚举 0-9 中不重复的数字按列或按整数判断等式注意最高位不能为 0。本质上都是同一个模板。这也是我把代码写成数组、而不是写死if (a[0] 祥)的原因——换个题目你只需要改映射关系。5. 从 P674 延伸出去这类竖式谜题的通用玩法刷完“三羊献瑞”之后很多同学会对竖式谜产生兴趣。这里简单聊聊几个经典版本方便你举一反三。5.1 经典英文版SEND MORE MONEY这是国外最著名的字母谜题之一S E N D M O R E ---------- M O N E Y解法思路和“三羊献瑞”几乎一样。最高位M一定是进位得到的 1然后从高位到低位一层层推。它比 P674 多一个变量总共 8 个不同字母规模差不多用 DFS 也很轻松。5.2 国产版羊年大吉系列类似这种“四字吉祥语相加”的题还有很多比如羊 年 大 吉 三 羊 献 瑞 --------------- 三 羊 生 瑞 气你看换了一层皮核心还是那个它。所以我才说P674 的价值不在于“记住答案是 1085”而在于你掌握了一个能解所有竖式谜的通用搜索框架。5.3 竞赛里怎么考蓝桥杯早年很喜欢把这类题目放在填空题或代码补全题里让你观察竖式、写 DFS 填空。现在更多是放到编程题里直接用dfs输出答案即可。从备赛角度我建议你把“全排列 判断等式”的写法练到肌肉记忆因为这类题虽然不难但考场上容易因为小细节丢分。尤其是 Python 选手permutations一行就能解决枚举省下大量时间。最后再说两句实际刷题的感受“三羊献瑞”是我很早就刷过的题当时先手推了一晚上推出来 1085 的时候特别有成就感。后来再看这道题才意识到手推固然爽但代码实现的思路才是真正能迁移的能力。如果你现在刚接触 DFS建议按这个顺序来先自己在纸上把竖式抄一遍试着用进位推一遍推不出来再看代码。这样你对used数组、回溯、剪枝的理解会深很多而不是单纯背模板。另外一个小经验刷 OJ 输出这种固定答案时如果题目允许直接输出答案你当然可以把cout 1085写死。但我还是建议保留 DFS 过程因为改题面、换等式的时候你只需要改竖式映射和判断逻辑不需要重新发明解法。希望这篇对你刷 P674 有帮助。如果你用这题的模板解出了别的竖式谜记得跑一下验证竖式别让手推的“看起来对”骗了你。