Automated Crossword Solving
Eric Wallace⋆ UC Berkeley、Nicholas Tomlin⋆ UC Berkeley、Albert Xu⋆ UC Berkeley、Kevin Yang⋆ UC Berkeley \ANDEshaan Pathak⋆ UC Berkeley、Matthew L. Ginsberg Matthew Ginsberg, LLC、Dan Klein UC Berkeley {ericwallace, nicholas_tomlin, albertxu3,
Abstract
We present the Berkeley Crossword Solver, a state-of-the-art approach for automatically solving crossword puzzles. Our system works by generating answer candidates for each crossword clue using neural question answering models and then combines loopy belief propagation with local search to find full puzzle solutions. Compared to existing approaches, our system improves exact puzzle accuracy from 71% to 82% on crosswords from The New York Times and obtains 99.9% letter accuracy on themeless puzzles. Additionally, in 2021, a hybrid of our system and the existing Dr.Fill system outperformed all human competitors for the first time at the American Crossword Puzzle Tournament. To facilitate research on question answering and crossword solving, we analyze our system’s remaining errors and release a dataset of over six million question-answer pairs.
中文速览
填写纵横字谜（crossword puzzle）不仅要理解线索（clue）的含义，还要让所有交叉格的字母同时吻合，这对机器来说极具挑战。伯克利纵横字谜求解器（Berkeley Crossword Solver, BCS）的思路是：先用基于BERT的双编码器（bi-encoder）问答模型为每条线索独立生成候选答案及其概率，再用循环置信传播（loopy belief propagation）在全局层面协调交叉字母约束，最后通过局部搜索迭代纠正残余错误，包括专门处理那些训练集里从未见过的稀奇答案。在《纽约时报》字谜上，整题完全答对的准确率从此前最优系统Dr.Fill的71%提升到82%，无主题字谜的字母准确率更达到99.9%；2021年美国纵横字谜锦标赛（ACPT）上，BCS与Dr.Fill的混合系统首次击败了所有人类选手。这项工作不仅推动了自动解谜的技术边界，还公开发布了超过600万对问答数据，为问答研究和约束满足研究提供了兼具挑战性与实用价值的新基准。
原文 arXiv:2205.09665;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2205.09665v2