Automated Crossword Solving

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

TL;DR

The Berkeley Crossword Solver (BCS) achieves state-of-the-art performance in automatically solving crossword puzzles by combining neural question answering with loopy belief propagation and local search. This system significantly outperforms previous methods and even human competitors in live tournaments, demonstrating a major leap in AI's ability to tackle complex linguistic and constraint-satisfaction problems.

What Problem Does This Paper Address?

Crossword puzzles, while a popular pastime, represent a significant challenge for Artificial Intelligence. They require not only a vast knowledge base and the ability to understand diverse linguistic phenomena (like wordplay, puns, and homophones) but also the capacity to reason about multiple intersecting answers simultaneously. Traditional AI approaches have struggled to achieve high accuracy, often failing to match the performance of expert human solvers. This paper aims to bridge this gap by developing a robust, end-to-end system that can automatically solve crossword puzzles with high precision.

Methods

The Berkeley Crossword Solver (BCS) employs a multi-stage approach:

  1. Neural Question Answering (QA): The system first uses a bi-encoder neural network, initialized with BERT, to generate candidate answers for each crossword clue. This model is trained to map clues and answers into a shared embedding space, allowing for efficient retrieval of likely answers. A key aspect is its "closed-book" nature, focusing on answers seen during training, which surprisingly proved more effective than open-book models for this task.
  2. Loopy Belief Propagation (BP): To handle the interconnectedness of crossword answers, BCS uses loopy belief propagation. This technique iteratively refines the probabilities of answers by considering the constraints imposed by intersecting words. BP is chosen for its ability to directly search for solutions maximizing expected overlap with the ground truth, rather than just likelihood, and for its generation of marginal distributions useful for subsequent steps.
  3. Local Search (LS): To further improve solutions and correct minor errors, a local search phase is applied. This involves proposing small edits to the puzzle (e.g., flipping uncertain letters) and scoring these proposals using a second-pass generative QA model (ByT5-small). This iterative refinement helps to fix errors that BP might miss.

Datasets

The paper introduces a new, large-scale dataset of over six million question-answer pairs collected from 26 publishers, including The New York Times, The LA Times, and USA Today. This dataset spans over 70 years of crossword puzzles and is unique in its diversity and expert validation. For evaluation, they used 2020 NYT puzzles for validation and held out other puzzles for testing. They also collected a smaller set of complete puzzle grids for final evaluation.

Key Insights and Ideas

  • "Closed-book" QA is surprisingly effective: The authors found that a "closed-book" QA model, which relies only on knowledge seen during training, performed better for crossword solving than open-book models that could access external knowledge like Wikipedia. This suggests that the specific nature of crossword answers and clues favors memorized patterns over broad knowledge retrieval.
  • Loopy Belief Propagation for Constraint Satisfaction: BP is a powerful tool for solving crossword puzzles because it directly optimizes for the correctness of intersecting words, not just the individual likelihood of each answer. This is crucial for handling the complex dependencies in a crossword grid.
  • Local Search as a Fine-Tuner: While BP gets the solver close, local search is essential for achieving near-perfect accuracy. It acts as a fine-tuning mechanism, correcting subtle errors that might otherwise prevent a perfect solve.
  • Crossword Puzzles as a Rich AI Testbed: The paper highlights crosswords as an excellent benchmark for AI, testing not only QA but also complex constraint satisfaction, reasoning under uncertainty, and handling of linguistic nuances like wordplay.

Key Results

  • State-of-the-Art Accuracy: The BCS achieves 82% exact puzzle accuracy on The New York Times crosswords, a significant improvement from the previous state-of-the-art 71%.
  • Near-Perfect Themeless Puzzles: On themeless puzzles, the system achieves an impressive 99.9% letter accuracy.
  • Human Competition Victory: In the 2021 American Crossword Puzzle Tournament (ACPT), a hybrid system incorporating BCS outperformed all 1033 human competitors, achieving a perfect score on 6 out of 7 puzzles.
  • Improved QA Recall: The bi-encoder QA model achieves 94.6% top-1000 recall on NYT test sets, outperforming Dr.Fill's 84.4%.

Limitations and Future Work

  • Themed Puzzles: The BCS struggles with "themed" puzzles, which often involve unique constraints like multiple letters in a single cell or topical connections between answers. The system does not explicitly handle these themes.
  • QA Errors: While significantly improved, QA errors remain a source of failure, particularly for wordplay and cross-reference clues.
  • Future Work: The authors suggest designing better evaluation metrics for automated crossword solvers, exploring methods for handling crossword themes, and potentially developing puzzle generation capabilities. They also emphasize the importance of their released dataset for future research in QA and crossword solving.

Summary updated

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.
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