题目重点：约束求解提供正确核心，分布式调度负责均衡和重试。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 给定board的word slots与dictionary，找任意完整可行填词，不要求最好评分。训练代码输入slots坐标，uppercase词表，交叉位置字母一致，reuse是否允许显式参数。
- 50×50、约100 slots、百万词是讨论规模，不证明每个实例单机必然超时。board图片、slot编号/线索映射未齐，不复原缺图；输出可行词后再映射线索。
解题路线
- 先将问题建CSP：slot为变量、匹配长度/固定字母词为domain、交叉格一致为约束。按长度和位置字母倒排缩候选，选最小remaining domain的slot分支，逐次propagate、失败回溯。
- 单机基线可证明当前assignment是否合法；本代码MRV动态扫描并追踪新写格，撤销不删被其他已填slot共享的字母。允许重复词与不允许不同，不从crossword名称推断。
- 分布式任务为immutable puzzle version+partial assignment+剩余分支范围。frontier初始拆较浅层，worker DFS扩展；长分支达到时间/工作预算后checkpoint并split更深子分支，短死分支worker继续偷取工作。
- scheduler存task lease/attempt，重试同partial branch允许重复搜索但不能丢分支。首个solution由独立validator核完整slots/字母/词表规则，再CAS job running→solved并广播cancel；重复solution不覆盖已提交结果。
- 无解结论比找到一解更严格：每个分支需完成证明，动态split parent只有在所有child已登记后才能标delegated，所有frontier exhausted才no-solution。timeout返回incomplete，不把任务暂时空队列当无解。
手动走一遍
两个交叉slot都长2，word AB/BA，交叉格限制可能排除一半组合；MRV先填固定字母最多slot，减少无用分支。worker拆parent后崩溃，若先标parent完成再登记children会漏搜索空间；需原子登记或可恢复split事件。3000个小例对全部笛卡尔assignment穷举核对有解/无解和返回是否合法。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def solve(slots,words,prefilled=None,reuse=False):
# slots: ordered sequences of hashable cells; solution maps slot index to word.
slots=[tuple(slot) for slot in slots];words=sorted(set(words));board=dict(prefilled or {})
if any(not slot or len(set(slot))!=len(slot) for slot in slots):raise ValueError('slot cells')
if any(not isinstance(word,str) or not word or not word.isascii() or not word.isalpha() or not word.isupper() for word in words):raise ValueError('uppercase ASCII words')
if any(not isinstance(value,str) or len(value)!=1 or not value.isascii() or not value.isupper() or not value.isalpha() for value in board.values()):raise ValueError('prefilled letters')
by_length={}
for word in words:by_length.setdefault(len(word),[]).append(word)
assignment={};used=set()
def candidates(index):
return [word for word in by_length.get(len(slots[index]),[]) if (reuse or word not in used) and all(cell not in board or board[cell]==letter for cell,letter in zip(slots[index],word))]
def search():
if len(assignment)==len(slots):return dict(assignment)
possibilities=[(candidates(i),i) for i in range(len(slots)) if i not in assignment]
options,index=min(possibilities,key=lambda pair:(len(pair[0]),pair[1]))
for word in options:
added=[cell for cell in slots[index] if cell not in board]
for cell,letter in zip(slots[index],word):board[cell]=letter
assignment[index]=word
if not reuse:used.add(word)
result=search()
if result is not None:return result
if not reuse:used.remove(word)
del assignment[index]
for cell in added:del board[cell]
return None
return search()
复杂度
候选域上限D、Sslots，最坏指数O(D^S)搜索，不能分布式后宣称多项式。代码每层重新筛候选有额外O(S×D×word_length)，词索引/传播可改善常数；完整百万词每worker复制需内存预算和共享索引。
易错点与追问
容易失分的边界
- 假设分发任务就能解决指数爆炸，缺候选剪枝。
- 超时/丢worker后宣布无解。
- 客户端提交solution不做独立合法性验证。
继续深挖
- 如何让dynamic split分支互不遗漏、可重复但可去重？
- 只要一解与要求全部解时，取消/结果存储协议怎样改变？
