Automated Crossword Solving

Eric Wallace, Nicholas Tomlin, Albert Xu, Kevin Yang, Eshaan Pathak, Matthew Ginsberg, Dan Klein

Abstract

Crossword puzzles represent a unique challenge for artificial intelligence, requiring both deep linguistic understanding and complex constraint satisfaction. We present the Berkeley Crossword Solver (BCS), a system that combines neural question answering with probabilistic inference. By utilizing a dense bi-encoder for answer generation, loopy belief propagation for grid-level constraints, and a generative local search for refinement, the BCS achieved a historic milestone by outperforming all human competitors at the 2021 American Crossword Puzzle Tournament.

Introduction

Crossword puzzles are a "grand challenge" for AI because they sit at the intersection of Natural Language Processing (NLP) and Constraint Satisfaction. Solving a puzzle requires decoding clues that are often intentionally misleading, filled with puns, or reliant on obscure trivia. Furthermore, because words intersect in a grid, every letter must satisfy two different clues simultaneously. This creates a massive search space where a single error can cascade. Previous systems like Dr. Fill relied on hand-crafted heuristics but struggled with the nuanced wordplay that human experts navigate easily.

Methodology

The Berkeley Crossword Solver approaches the problem through a three-stage pipeline designed to balance linguistic intuition with logical consistency.

The three-stage pipeline of the Berkeley Crossword Solver: Question Answering, Loopy Belief Propagation, and Local Search.

1. Bi-Encoder QA Model

The system first generates candidate answers for every clue using a "closed-book" bi-encoder based on BERT. This model maps clues and potential answers into a shared vector space. Unlike traditional search engines, it relies on knowledge embedded in its parameters from training on 6.4 million past clue-answer pairs, allowing it to capture the idiosyncratic nature of crossword language.

2. Loopy Belief Propagation (BP)

To reconcile the intersecting constraints of the grid, the system uses Loopy Belief Propagation. BP passes messages between intersecting words to calculate the marginal probability of each letter in each cell. This allows the system to resolve conflicts—for instance, if a high-probability answer for an "Across" clue conflicts with a "Down" clue, BP shifts the probability distribution toward a mutually compatible solution.

3. Local Search with Generative Refinement

The final stage involves a local search to "polish" the solution. The system identifies uncertain areas and proposes small edits (1-2 letter flips). These edits are scored using a second-pass generative model (ByT5), which allows the system to "invent" answers not seen in the training set, such as multi-word phrases or rare crossword fill.

Evaluation and Results

The researchers trained the BCS on a dataset of 6.4 million clue-answer pairs from 26 publishers (1951–2019). The system was evaluated on puzzles from 2020 and 2021, as well as a live performance at the 2021 American Crossword Puzzle Tournament (ACPT).

Comparison of Top-k Accuracy between the BCS QA model and the previous state-of-the-art, Dr. Fill.

The BCS represents a significant advancement over previous technology. On New York Times puzzles, it improved exact puzzle accuracy from 71% (Dr. Fill) to 82%. Most notably, at the 2021 ACPT, a hybrid version of the system scored higher than all 1,033 human contestants, marking the first time an automated system has won the event. Despite its complexity, the system remains efficient, solving a typical puzzle in approximately 10 seconds.

Discussion and Limitations

A key insight from this work is that neither pure NLP nor pure search is sufficient; the hybrid approach of bi-encoder "intuition" and BP "logic" is essential. Furthermore, "closed-book" models trained specifically on crossword history outperformed general-purpose web-search models.

However, "themed" puzzles remain a significant challenge. Many crosswords feature gimmicks, such as "rebus" squares (multiple letters in one box) or non-standard reading directions. Because the BCS assumes a standard grid, it is currently limited in handling these creative constructions. Future work will focus on integrating theme-detection modules to address these more complex puzzle types.

This summary is based on "Automated Crossword Solving" by Wallace et al., published in the Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (2022).

Summary updated

BibTeX
@inproceedings{wallace2022automated,
  author = {Eric Wallace and Nicholas Tomlin and Albert Xu and Kevin Yang and Eshaan Pathak and Matthew Ginsberg and Dan Klein},
  title = {{Automated Crossword Solving}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2022},
  url = {https://openreview.net/forum?id=SbAqrmWd63},
}
Figure