王都的炼金工坊

王都的炼金工坊停工了。

不是爆炸。爆炸反而好处理，扫干净，赔钱，写检讨，下次别把月光和硫磺放在同一个抽屉。

问题是炉墙吐紫烟。

墙上有很多炼制槽，每个槽嵌着三枚古老符文。上面两枚同时点亮，应该使下面那枚亮成恰好的颜色；若火焰多出一丝，火星会沿暗沟钻进左边的槽。所有符文都有自己的火温，互不相同。一枚符文可以在很多槽里重复出现，但它的火温一生不变。

总工长决定把错误找出来。

他从最右边的槽开始，依次检查上符文、下符文、结果符文；检查完一槽，就挪到左边一槽。某个叫作 A 的符文在第五个槽里又出现，他又记了一遍它的火温。到了第八个槽，A 再次露面，他还是记了一遍。

学徒说，A 的火温刚才已经记过。

“我知道，”总工长说，“可这是第八个槽。”

他忙了一夜，记满十七张羊皮纸。炉墙也很配合地继续吐紫烟。没有任何一个槽凑齐足够的已知火温，能指出事情从哪里开始坏掉；火星到底从哪来，只好被总工长先各猜一遍。

清炉的老大爷(对，不是看门的牢大爷)早晨来倒灰。

他把十七张纸拿去垫炉脚，又另拿了一张小纸条，在上面写下：A、F、C、D……每个符文只写一次。写到一枚新符文，才让学徒试一种新火温。那些右边槽里先凑齐的三枚符文，很快开始自己作证：有的无论火星来没来，颜色都对不上；有的能把火星逼到下一槽去。

紫烟先从哪里冒出，终于变成了一个可以回答的问题。

总工长看着那张很短的纸条，沉默很久。

炉墙上的槽，从来只是符文碰头的地点。

简化题面

┌─ [P1092] 虫食算
├─ 平台: 洛谷
├─ 题意: 给定一个 N 进制加法竖式。前 N 个大写字母各代表 0 到 N-1 中一个不同的数。
├─ 输入: 第一行 N；随后三行 N 位字符串，前两行相加得到第三行。
├─ 输出: 按 A、B、C... 的顺序输出各字母对应的数。
├─ 数据范围: 1 <= N <= 26；前 N 个字母均至少出现一次；输入保证唯一解。
├─ 关键限制: 三个字符串等长，允许前导 0，字母与数字是一一对应关系。
└─ 完整题面: https://www.luogu.com.cn/problem/P1092

竖式很像搜索顺序

P1092 很容易让人沿着竖式写 DFS。

从最低位开始。当前列先处理第一个加数，再处理第二个，最后推出结果位；进位自然传向高位。第一版就是这样写的。它并非裸枚举：某列的两个加数一旦有值，就尽量检查结果；已经不可能的进位链，会立刻停下。

模型没错。保存下来的 test 7 和 test 8 却都没有在时限内结束。

当时最自然的反应是：剪枝还不够强。

这也是搜索题最诱人的误诊，回家的诱惑。树太大时，眼睛会先盯住树枝。多写一个 if，多猜一种进位，多换一个枚举方向。在努力了！

但第一版还有一个更早的问题：递归层到底在决定什么？

它按“第几列、第几行”向前走。一个字母若在五个位置出现，程序就会五次走到它面前，确认“它已经有值”，然后继续。那些层次保留了竖式的版面，却没有产生新的选择。

格子是字母出现的位置。

变量是字母本身。

这两个词看起来很接近。

五十二万份天气预报

有一条尝试，尤其诚实地，暴露了这个误诊。

既然每一列都受进位影响，那先把所有进位猜完。进位已知时，列里的关系会简单很多；有时两个字母一确定，第三个字母甚至可以直接推出。

加强约束。

代码实际做的是：先枚举一张进位 mask，再从头启动一次字母搜索。最低位进位必须为 0，已经排除一半；当 N = 20 时，外层仍有 2^19 = 524288 种 mask。

进位原本可以由低位的真实赋值一路传上来。现在它被提前登记成五十二万份可能的天气预报。每一份预报都要重新把字母问题问一遍。

训练记录里，这条路同样 TLE。

进位在这里被放错了位置。这个弯路留下了一个更基本的区分：

能由已经作出的决定推出来的量，是传播结果；
必须主动从多个可能中选择的量，才是搜索变量。

把前者升级成后者，不会消灭未知。

只会给未知加班。

让最早能形成的约束先开口

最终版本没有为每个格子建递归层。它把字符串反转，从低位向高位扫描；每个字母第一次出现，才进入 trace。

void add(int letter) {
    if (vis[letter]) return;
    vis[letter] = true;
    trace.push_back(letter);
}

for (int i = 0; i < n; i++) {
    add(a[i]);
    add(b[i]);
    add(c[i]);
}

add() 会跳过已经见过的字母。于是 DFS 的每一层只给一个尚未赋值的字母选数字。

递归骨架也因此只认 trace[pos]，不再认“现在走到第几列、第几行”。

void dfs(int pos) {
    if (cut()) return;
    if (pos == trace.size()) {
        if (ok()) print_answer();
        return;
    }

    int letter = trace[pos];
    for (int value = mod - 1; value >= 0; value--) {
        if (used[value]) continue;
        num[letter] = value;
        used[value] = true;
        dfs(pos + 1);
        used[value] = false;
        num[letter] = -1;
    }
}

N 个字母仍要对应 N 个不同数字；坏情况下，排列的阴影还在。trace 改变的是每个约束何时拿到足够的信息。

真正改变的是约束被激活的时间。

低位的一列要说“这条分支错了”，得先看见它涉及的几个字母。按低位首次出现顺序，这些字母会更早被赋值。一旦三者凑齐，局部加法关系就有资格反对当前分支；若先填一串与它无关的高位字母，递归深度增加了，信息却没增加。剪枝函数只能站在旁边，状若小弟。

最终的局部检查故意不装作全知。三个字母都已知、但这一列的真实进位还不能由当前局部确定时，它只问一件事：进位为 0 或 1，是否至少有一种可能？

if ((x + y + 1) % mod != z &&
    (x + y) % mod != z)
    return true;

两种都不成立，才剪。

这段检查只在两种进位都失败时剪枝，给出的是局部的“不可能”证据。真正的 ok() 留在叶子，从最低位开始传播唯一的真实进位，完整核验整个竖式。

bool ok() {
    int carry = 0;
    for (int i = 0; i < n; i++) {
        int x = num[a[i]], y = num[b[i]], z = num[c[i]];
        if ((x + y + carry) % mod != z) return false;
        carry = (x + y + carry) / mod;
    }
    return carry == 0;
}

一个是安全的局部反驳。

一个是完整的最终判决。

变量顺序把前者送到足够早的地方， POWER。

所以那句容易被记成口号的话，应该说得更精确一些：

搜索顺序，决定，约束在第几层拿到足够的信息。

约束，越早能说“不”，后面越多的递归层，一剪梅。

代码终于不是在模仿纸面

重写时也没有自动顺利。init() 一度忘了调用，未赋值的 num[] 被当成了 0；完整检查一度忘记更新进位；调试输出也曾留在答案里。

三处 bug 分别落在初始化协议、列间状态协议和评测输出协议上。结构变好以后，普通 bug 仍然会照常上班。

目前可以确认的结果也很朴素：2026-08-26 重新以 C++17 -O2 编译最终源码，P1092 保留的 test 7、test 8 输出均与对应答案文件一致。训练记录标为 AC，但仓库没有保存可归属的提交记录，也没有各版本的可靠耗时；文章不把这两份保存测试写成完整评测复现。

证据边界同时给出了下一轮实验：为不同变量顺序增加节点计数，记录每种剪枝第一次可触发的深度，再比较低位优先和其他顺序。

下一次 DFS 慢下来

别急着问“这个 if 还能不能再强一点”。

先把纸面上的格子、边、公式和位置划掉，另外写下真正的未知量。然后问：

这一步是在作一个新决定，还是只是在经过同一个变量的另一次出现？
哪几个变量一齐确定后，第一条有杀伤力的约束才会成立？
哪些量应该沿约束自动传播，而不该提前升级成独立的猜测？

有些搜索题最终确实需要更强的剪枝、更聪明的启发式，甚至更换算法。

但在那之前，先让问题有机会说话。

炉墙从右边开始积起火星。

先调符文。

紫烟会比你先看见错误。