The Berkeley Crossword Solver

Eshaan Pathak Nicholas Tomlin Eric Wallace
Albert Xu Kevin Yang Dan Klein
{eshaanpathak, nicholas_tomlin, albertxu3, ericwallace, yangk}@berkeley.edu
We built an automated crossword solver using state-of-the-art neural network models for open-domain question-answering and assorted techniques for constraint satisfaction solving. Our system, known as the Berkeley Crossword Solver, is designed to solve American-style crossword puzzles like The New York Times Crossword. These crosswords often involve challenging themes, puns, and world knowledge and typically range in grid size from 15x15 to 21x21.
An example crossword grid Figure: An example crossword grid.
Our solver follows a two-step process. First, given a set of clues, generate potential answers using a dense passage retrieval model trained on existing publicly available crossword data. We then assign a calibrated probability to each generated candidate answer and feed these into a constraint solver. We're currently using Matt Ginsberg's Dr. Fill as our constraint solver, but are experimenting with other methods as well. Combined with Dr. Fill, we believe our system is the strongest automated crossword solver in the world, on par with the best human solvers.