OpenAI 填字游戏题目的完整解答：说明单机为何不够、带回溯与约束传播、位集候选过滤、将搜索树拆分为任务、工作窃取、提前终止、失败情形与替代方案。

作者：The Forward Deployed 编辑团队Reviewed

本文属于 OpenAI 系统设计题库。该题目具有该轮面试的代表性。分析与解法为本站原创。

问题描述

该服务接收一个网格描述和一个词典，返回一种将单词填入空格的方案，使得每个交叉字母都匹配。线索提示被忽略；生成网格不在范围内；只需给出一个解。

面试官并不想看到最巧妙的单机算法。据反馈，考察预期是一个分布式作业系统：先证明单机太慢，然后将搜索拆分到多个 worker 上，处理死路和卡住的 worker，并在某个 worker 找到答案时让所有人停止。把一小时都花在调优算法上的候选人会失败。

澄清问题

  • 网格大小？ 大约 50 × 50，约 100 个空格，长度 3 到 15。
  • 词典？ 大约一百万个单词，仅含大写字母。
  • 延迟要求？ 几分钟可以接受。作业异步运行。
  • 解一定存在吗？ 不一定。如果无解，系统最终必须给出结论，或在时限后放弃。
  • 单词可以重复吗？ 假设不可以。
  • 负载情况？ 每天提交大量谜题，因此系统应共享一个 worker 池。

难点在哪里

搜索空间极其庞大。一个长度为 7 的空格可能有数万个词典候选词。有 100 个空格时，原始赋值数量是这些数量的乘积，一个有数百位数字的数。没有任何机器能枚举它。

剪枝能消掉大部分：一旦放置一个单词，交叉的空格就有了固定字母，其候选列表随之缩小。但困难的网格仍会留下一个有数十亿节点的搜索树，而且其形状不可预测。一个分支在几毫秒内就死掉；另一个分支运行一小时后才失败。

因此核心矛盾是并行性与搜索的不规则形状。拆分工作很容易；真正的难题是让每个 worker 在一棵子树之间相差数个数量级的树上保持忙碌。

flowchart TB R[Empty grid]:::svc --> A1[Slot 12 = ORBITAL]:::svc R --> A2[Slot 12 = CAPITAL]:::svc R --> A3[Slot 12 = ...]:::svc A1 --> B1[Slot 7 = ...]:::svc A1 --> B2[dead end]:::bad A2 --> B3[Slot 7 = ...]:::svc B3 --> C1[... 100 levels deep]:::svc classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef bad fill:#fbe9e4,stroke:#c4492d,color:#171717;
关键思路。 用两分钟证明单机太慢，然后把整轮时间花在拆分不规则的搜索树和让 worker 保持忙碌上。

核心概念

回溯搜索

对赋值进行深度优先搜索：选择一个槽位，尝试一个候选词，检查一致性，递归，失败时撤销。它占用内存很少，因为只保存当前路径。

约束传播

放置一个词后，将每个交叉槽位的候选列表更新为匹配新固定字母的词。如果任何列表变为空，立即回溯，而不是在许多层之后才发现死路。

最受约束变量优先

选择剩余候选最少的槽位作为下一个。它在注定失败时尽早失败，从而在树的顶部附近剪枝，而那里的剪枝收益最大。

工作窃取

空闲的工作者从忙碌工作者的未探索工作中取走一部分。它无需预先知道树的形状就能平衡一棵不规则的树。

核心思想。 每个工作者在深度优先搜索中结合传播和智能槽位选择；工作者之间进行工作窃取。

需求

继续阅读之前。 请陈述功能需求，以及当解存在时系统必须具备的一个性质。

1.1 功能需求

  • 接受一个网格（包含位置、方向、长度的槽位）和一个词典。
  • 返回一个有效填充，或报告在时限内未找到解。
  • 让客户端可以查询状态和取消。
  • 在多个谜题之间共享一个工作者池。

1.2 非功能需求

  • 完备性：如果解存在，只要时间足够，搜索最终会找到它。
  • 速度：典型的困难网格在几分钟内完成。
  • 利用率：工作者保持忙碌直到任务结束。
  • 容错性：一个失效的工作者最多丢失其当前任务，该任务会被重做。
  • 及时终止：当一个工作者成功时，所有其他工作者在几秒内停止。

1.3 约束与性质

完备性是性质：任何分支都不能被丢弃。不规则的工作是约束：任务大小未知，这决定了拆分和窃取的设计。

粗略估算

  • 每个槽位的候选词：常见长度可达数万个。有 100 个槽位时，未剪枝的乘积远超 10^100。
  • 剪枝后的搜索：一个困难网格可能仍需要数十亿个节点。以每核每秒 100 万个节点计算（每个节点用位集操作过滤候选列表），100 亿个节点需要 10,000 核秒，单核约 3 小时，200 核约 1 分钟。
  • 内存中的词典索引：100 万个词；每个（长度、位置、字母）组合一个位集，共 15 × 15 × 26 ≈ 5,850 个位集。如果每个位集只覆盖其长度的词，最大的长度桶可能包含约 150,000 个词，每个位集 19 KB，因此整个索引大约 100 MB。每个工作者持有一份副本。
  • 任务消息：一个任务是一个部分赋值，几百字节。即使 100,000 个任务也微不足道。
核心思想。 单核需数小时，几百核只需一分钟。索引能装进每个工作者；任务非常小。

API 设计

POST /v1/puzzles
  {slots: [{id, row, col, dir: "across"|"down", length}], dictionary_id, time_limit_s}
  -> 202 {job_id}
GET  /v1/puzzles/:job_id
  -> {status: queued|running|solved|unsolvable|timed_out|cancelled,
      solution?: {slot_id: word}, nodes_explored, elapsed_s}
POST /v1/puzzles/:job_id/cancel

POST /v1/dictionaries   {words[]} -> {dictionary_id}   // preprocessed into bitsets once

内部：

task = {job_id, task_id, assignment: {slot_id: word}, parent_task_id, depth}
worker -> coordinator: lease_task, report {task_id, result: solved|exhausted|split, subtasks[]}
coordinator -> workers: stop {job_id}

数据模型

jobs   (job_id, status, grid_ref, dictionary_id, time_limit_s, solution_json,
        created_at, finished_at, nodes_explored)
tasks  (job_id, task_id, assignment_json, status: queued|leased|done,
        worker_id, lease_expires_at, attempt)
solved flag: Redis key job:{job_id}:solved  (plus pub/sub channel job:{job_id}:stop)
dictionary index: files per dictionary_id, loaded into worker memory

只有当每个任务都无解完成时，整个作业才算完成且无解。按作业跟踪未完成的任务可以让这个判断变得精确。

高层设计

5.1 单机暴力法

按顺序枚举所有分配方案。永远跑不完。

5.2 修复 1：单机上带传播的回溯

深度优先搜索，优先处理约束最多的槽位，每次放置后做前向检查，并用位集过滤候选词。简单的网格几秒钟就能完成，困难的网格仍需数小时。

5.3 修复 2：把搜索树拆成任务

选择约束最多的规则对应的第一个槽位，为每个候选词创建一个任务：每个任务就是一棵子树。如果这样产生的任务对任务池来说太少，就再展开一层。把任务放入队列；工作节点租用任务并在其下方运行 DFS。

flowchart LR CO[协调器]:::svc -->|种子任务：树顶| TQ[[任务队列]]:::new TQ --> W1[工作节点 1：DFS]:::svc TQ --> W2[工作节点 2：DFS]:::svc TQ --> W3[工作节点 N：DFS]:::svc W1 -->|已解出 / 已穷尽 / 拆分| CO classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef new fill:#ffffff,stroke:#c4492d,stroke-width:2px,stroke-dasharray:5 3,color:#171717;

5.4 修复 3：动态拆分与工作窃取

静态任务的工作量并不均衡。当队列快耗尽时，繁忙的工作节点会拆分自己剩余的搜索前沿，并把其中一部分推回队列。空闲的工作节点也可以直接向繁忙的工作节点请求一部分工作。

5.5 修复 4：提前终止

第一个找到解的工作节点写入解、设置已解决标志，并发布停止消息。其他工作节点每处理几千个节点就检查一次标志，然后停止。

5.6 组合后的设计

sequenceDiagram
  autonumber
  actor C as Client
  participant CO as Coordinator
  participant Q as Task queue
  participant W as Workers
  participant R as Redis flag
  C->>CO: submit grid
  CO->>CO: propagate, choose first slots, seed ~10x workers tasks
  CO->>Q: tasks
  loop until solved or all tasks exhausted
    W->>Q: lease task
    W->>W: DFS below task, check flag every 4k nodes
    alt queue low
      W->>Q: push half of own frontier
    end
    W->>CO: exhausted or split
  end
  W->>R: solved (first writer wins)
  W->>CO: solution
  CO->>W: stop job (pub/sub)
  CO-->>C: solution
核心思想。 在每个工作节点上做传播，播种大量任务，通过拆分和窃取来重新平衡负载，并在第一个解出现时让所有人停止。

深入探讨

6.1 证明单机太慢

继续阅读之前。 给面试官一个两分钟的估算，说明需要分布式设计。

使用整数估算。假设在交叉关系未知之前，每个槽位平均有 10,000 个候选词。传播会大幅缩小后续槽位的候选集，因此假设在前几层之后，有效分支因子降到每层约 1.3。顶层仍然有数千个分支。即使按 10,000 × 1,000 × 100 × 1.3^90 计算，最坏情况下也超过 10^19 个节点。得益于剪枝，真正困难的网格远低于这个数字，但仍达到数十亿量级。按每秒一百万个节点计算，十亿个节点约需 17 分钟，一百亿个节点约需 3 小时。这足以证明并行化的必要性；不要在这上面花更多时间。

6.2 快速候选过滤

对于每个单词长度 L，为每个（位置，字母）组合维护一个位集：如果长度为 L 的第 i 个单词在该位置上是该字母，则第 i 位被置位。对于长度为 7、模式为

A _ _ L E _ _

是三个位集的按位与：A 在第 0 位，L 在第 3 位，E 在第 4 位。统计置位的数量即可得到候选数量，用于选择最受约束的槽位。这些操作在机器字上运行，每次处理 64 位。

再用一个位集跟踪已使用的单词，以防止重复。

6.3 拆分工作

在继续阅读之前。 你有 200 个 worker。你会在开始时创建多少个任务？如何创建？

预置大约 10 倍于 worker 数量的任务，约 2,000 个，这样已完成的任务能留出重新平衡的空间。协调器将搜索运行到一个较浅的深度：选择最受约束的槽位，对其候选进行分支，传播约束，并以广度优先的方式继续，直到前沿至少有 2,000 个节点。每个前沿节点成为一个任务。

合理地对队列排序：剩余槽位候选更多的任务更可能包含解。有些系统还会随机化顺序，这在解集中在少数子树时会有帮助。

6.4 负载均衡

子树之间的规模相差几个数量级。如果采用静态任务，大多数 worker 会早早完成并等待，而少数几个则在巨大的子树中苦苦挣扎。

两种动态机制可以解决这个问题。

按需拆分。 worker 的 DFS 栈在每一层保存着其未探索的兄弟节点。当全局队列低于某个阈值时，忙碌的 worker 会把最靠近根节点的未探索兄弟节点——也就是剩余最大的子树——推回队列作为新任务。

窃取。 空闲的 worker 向随机的忙碌 worker 请求工作；忙碌的 worker 会交出一半其最浅层的未探索兄弟节点。随机化窃取在理论和实践中都能很好地平衡负载。

无论哪种方式，任务都是一个部分赋值，因此转移工作的成本只有几百字节。

区分答案水平的关键点：负载均衡

弱静态拆分

只对树做一次划分，然后等待最慢的 worker。

良好许多小任务

预置远多于 worker 数量的任务，让完成得快的 worker 领取更多任务。

强动态拆分或窃取

在队列不足时拆分最大的未探索子树，或让空闲 worker 从忙碌 worker 那里窃取任务，并解释为什么最浅层的兄弟节点是应该交出去的部分。

6.5 提前终止

每个作业在 Redis 中有一个 solved 标志，使用 set-if-not-exists 写入，因此只有第一个解会被计入。求解器还会在每个作业的频道上发布一条停止消息。worker 每处理几千个节点就检查一次该标志，成本仅几微秒，作为错过消息时的兜底。协调器将作业标记为已解决并丢弃其剩余任务。

6.6 故障与完备性

任务以超时和心跳的方式被租用。如果某个 worker 死亡，其租约过期，任务会返回队列。租约过期后的重复工作是无害的，因为搜索没有副作用；如果两个 worker 求解了同一个子树，先写入者胜出。

完整性要求精确的记账。只有当某个 worker 报告其任务已穷尽，或者它拆分出的所有任务都已被核算时，任务才被标记为完成。拆分会在一步中创建子任务，并将父任务的剩余工作标记为已移交。只有当未完成任务的数量降为零且没有解时，任务才算不可解。

长任务可以报告检查点：即当前路径。重试的任务随后从死掉的 worker 停止的地方附近恢复，而不是重复数小时的搜索。

6.7 多个谜题

许多任务共享 worker 池。在各个任务之间公平调度，并为每个任务设置最大 worker 占用份额，这样某个超大谜题就不会饿死短任务。强制执行每个任务的时间限制：一旦超时，协调器停止该任务并报告“超时”。

6.8 worker 的搜索，用代码实现

在继续阅读之前。 请写出深度优先搜索的核心部分，包括 worker 在哪里检查停止标志，以及它如何移交工作。
def solve(assignment, domains, stop, stats, give_away):
    # assignment: slot -> word; domains: slot -> bitset of remaining candidates
    if all(slot in assignment for slot in domains):
        return assignment
    stats.nodes += 1
    if stats.nodes % 4096 == 0 and stop.is_set():
        raise Stopped()

    slot = min((s for s in domains if s not in assignment),
               key=lambda s: popcount(domains[s]))          # most constrained first
    for word in candidates(domains[slot]):
        new_domains = forward_check(domains, slot, word)    # None if any crossing is empty
        if new_domains is None:
            continue
        if give_away.requested():                           # another worker is idle
            give_away.push(remaining_siblings(slot, word))  # hand off untried words at this level
        result = solve({**assignment, slot: word}, new_domains, stop, stats, give_away)
        if result:
            return result
    return None

指出三点：停止检查开销小且周期性执行；

forward_check

在任何域为空时提前返回；并且在 worker 注意到请求的最浅层级移交工作，因为那里未尝试的兄弟节点是可用的最大子树。真正的实现会在写入时复制位集，并在回溯时撤销更改，而不是复制字典，从而保持内存占用平稳。

6.9 判断网格何时过难

有些网格没有解，有些则需要数天时间。为每个任务设置时间限制和节点预算。诚实地报告进度：已探索的节点数、达到的最深点以及未完成的任务数。当达到限制时，返回“超时”并附带这些数字，帮助用户决定是放宽网格还是放宽词典。

对剩余工作量的良好估计会有所帮助：在树中随机采样若干路径，并根据观察到的分支情况估计树的大小，这种技术被称为 Knuth 估计器。它很粗糙，但当用户询问是否值得等待时，总比没有好。

区分答案的关键：搜索本身

弱无剪枝的伪代码

使用朴素的递归，没有槽位排序、没有前向检查、没有停止检查。

良好带剪枝的搜索

选择约束最多的槽位，并在任何交叉槽位变空时立即回溯。

强为分布式而构建的搜索

增加周期性停止检查，在收到请求时移交最浅的未尝试兄弟节点，通过撤销操作保持内存平稳，并在限制条件下报告进度。

变体

7.1 随机局部搜索

用随机候选填满网格，然后逐步修复冲突，就像模拟退火或最小冲突搜索那样。它在大型、宽松的网格上可能很快，但无法证明不存在解。它极易并行化：用不同的种子运行多个独立搜索。任务系统保持不变。

7.2 找出所有解

去掉提前终止并收集所有解。完整性记账变得更加重要，输出可能非常庞大；应采用流式输出。

7.3 SAT 求解器

将槽位和交叉点编码为布尔约束，并使用 SAT 求解器。组合式求解器并行运行多种策略，一旦某个策略成功即停止，这在更高层次上是同样的分布式模式。

7.4 当谜题数量扩大十倍时

当并发谜题很多时，工作池就变成了一个共享调度器问题。给每个任务分配一部分 worker，优先处理短任务使其快速完成，并将任何单个任务限制在工作池的一小部分以内。词典索引在 worker 上是所有任务共享的只读内存。

可迁移的模式

这就是带动态负载均衡的分布式树搜索。同样的模式可以解决调度问题、定理证明、博弈树搜索以及带提前停止的超参数搜索：播种大量小任务，在 worker 空闲时进行拆分或窃取，把副作用排除在搜索之外以便重试零成本，并对未完成的工作进行精确记账，使“未找到”这一结论可信。

回顾：30 秒答案

  • 说明单机为何会失败。 剪枝后仍有数十亿节点；单核需要数小时。
  • 每个 worker 使用智能 DFS。 优先处理约束最多的槽位、前向检查、位集过滤器。
  • 为每个 worker 播种约十个任务。 以浅层前沿节点作为部分赋值。
  • 拆分最大的剩余子树或按需窃取。 让每个 worker 都保持忙碌。
  • 快速停止；精确记账。 用已解决标志加 pub/sub；只有当未完成任务数归零时才判定无解。

测验

+为什么面试官会引导你避开算法优化？

这道题考察的是分布式系统设计：拆分工作、平衡一棵不规则的树、处理故障以及提前停止。更快的单机算法仍然无法解决这些问题。

+前向检查的作用是什么？

放置一个单词后，它会把每个交叉槽位的候选词缩小到符合新字母的单词。如果任何槽位没有剩余候选词，搜索立即回溯。

+为什么拆分时要交出最靠近根节点的未探索兄弟节点？

它们是最大剩余子树的根，因此每个被移动的任务都携带大量工作。移动微小的深层子树，其协调成本会超过节省的开销。

+为什么租约过期后的重复工作在这里是无害的？

搜索没有副作用。两个 worker 探索同一子树会浪费一些时间，但不会破坏任何东西，而且只有第一个解会被记录。

+系统何时可以报告不存在解？

只有当所有任务（包括所有拆分出的任务）都被报告为已穷尽，即未完成任务数在没有找到解的情况下归零时。

+为什么每隔几千个节点才检查一次停止标志？

每次检查的成本很小；节点每秒会被处理数百万次。每隔几千个节点检查一次带来的开销可以忽略不计，同时仍能在几毫秒内停止工作进程。

+为什么求解器是完备的，却还需要时间限制？

有些网格无解，或者需要数天才能求解完毕。设置限制后，可以返回一个带有进度数据的明确答案，而不是无休止地运行下去。

参考资料与延伸阅读

NextDesign Google Calendar