Automated Crossword Solving (2022)

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 57% to 82% on crosswords from The New York Times and obtains 99.9% letter accuracy on themeless puzzles. Our system also won first place at the top human crossword tournament, which marks the first time that a computer program has surpassed human performance at this event. 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 dataset this section describes the dataset that we built for training and evaluating crossword solving systems. recall that a crossword puzzle contains both question-answer pairs and an arrangement of those pairs into a grid (e.g., figure 1 ). unfortunately, complete crossword puzzles are protected under copyright agreements; however, their individual question-answer pairs are free-to-use. our dataset efforts thus focused on collecting numerous question-answer pairs (section 2.1) and we collected a smaller set of complete puzzle grids to use for final evaluation (section 2.2). ## resolving letter constraints using bp given the list of answer candidates and their associated probabilities from the first-pass qa model, we next built a solver that produces a puzzle solution dr.fill qa is an existing crossword qa system that ensembles tfidf-like scoring with numerous additional scoring modules. our neural bi-encoder model improves top-1000 accuracy from 84.4% to 94.6%. we use belief propagation @xcite , henceforth bp, for two reasons. first, bp directly searches for the solution with the highest expected overlap with the ground-truth solution, rather than the solution with the highest likelihood under the qa model @xcite . this is advantageous as it maximizes the total number of correct words and letters in the solution, and it also avoids strange solutions that may have spuriously high scores under the qa model. second, bp also produces marginal distributions over words and characters, which is useful for generating an n-best list of solution candidates (used in section 5). ## iteratively improving puzzle solutions many of the puzzle solutions generated by bp are close to correct but have small letter mistakes, e.g., nauci instead of fauci or tazoambassadors instead of jazzambassadors, as shown in figure 4 . 4 we remedy this in the final stage of the bcs with local search (ls), where we take a "secondpass" through the puzzle and score alternate proposals that are a small edit distance away from the bp solution. in particular, we alternate between proposing new candidate solutions by flipping uncertain letters and scoring those proposals using a second-pass qa model. proposing alternate solutions similar to related problems in structured prediction @xcite or model-based optimization @xcite , the key challenge in searching for alternate puzzle solutions is to avoid false positives and adversarial inputs. if we score every proposal within a small edit distance to the original, we are bound to find nonsensical character flips that nevertheless lead to higher model scores. we avoid this by only scoring proposals that are within a 2-letter edit distance and also have nontrivial likelihoods according to bp or a dictionary. specifically, we score all proposals whose 1-2 modified letters each have probability 0.01 or greater under the character marginal probabilities produced by bp. 5 we also score all proposals whose 1-2 modified letters cause the corresponding answer to segment into valid english words. 6 scoring solutions with second-pass qa given the alternate puzzle solutions, we could feed each of them into our bi-encoder model for scoring. however, we found that bi-encoders are not robustthey sometimes produce high-confidence predictions for the nonsensical answers present in some candidate solutions. we instead use generative qa models to score the proposed candidates as we found these models to be empirically more robust. we finetuned the character-level model byt5small @xcite on our training set to generate the answer from a given clue. we then score each proposed candidate using the product of the model's likelihoods of the answers given the clues, j p (a j | c j ). after scoring all candidate proposals, we apply the best-scoring edit and repeat the proposal and scoring process until no better edits exist. figure 4 shows an example of the candidates accepted by ls. quantitatively, we found that ls applied 243 edits that improved accuracy and 31 edits that hurt accuracy across 234 nyt test puzzles. 5 the character-level marginal distribution for most characters assigns all probability mass to a single letter after a few iterations of bp (e.g., probability 0.9999). we empirically chose 0.01 as it achieved the highest validation accuracy. 6 for instance, given a puzzle that contains a fill such as munnyandclyde, we consider alternate solutions that contain answers such as bunnyandclyde and sunnyand-clyde, as they segment to "bunny and clyde" and "sunny and clyde." ## end-to-end system results we evaluate our final system on our set of test puzzles and compare the results to the state-of-theart dr.fill system @xcite . we compute three accuracy metrics: perfect puzzle, word, and letter. perfect puzzle accuracy requires answering every clue in the puzzle correctly and serves as our primary-and most challenging-metric. themed vs. themeless puzzles although the bcs achieves equivalent or worse letter accuracy on newsday and la times puzzles, it obtains substantially higher puzzle accuracy on these splits. we attribute this behavior to errors concentrated in unique themed puzzles, e.g., ones that place multiple letters into a single cell. to test this, we break down nyt puzzles into those with and without special theme entries (see appendix d for our definition of theme puzzles). on themeless nyt puzzles, we achieve 99.9% letter accuracy and 89.5% perfect puzzles, showing that themed puzzles are a major source of our errors. note that the dr. the atlantic 46 82.6 89.1 98.5 99.1 99.7 99.8 newsday 52 86.2 94.2 98.6 99.6 99.1 99.8 the new yorker 22 86.4 77.2 99.5 98.9 99.9 99.8 the la times 54 81.5 92.6 99.4 99.7 99.9 99.9 the new york times 234 70.5 81.7 97.9 98.9 99.2 99.7 american crossword puzzle tournament for our last evaluation, we submitted a system to participate live in the american crossword puzzle tournament (acpt), the longest-running and most prestigious human crossword tournament. our team obtained special permission from the organizers to participate in the 2021 version of the tournament, along with 1033 human competitors. for the live tournament, we used an earlier system, which does not use belief propagation or local search but instead uses dr.fill's constraint-resolution system along with the bcs qa modules described above. the submitted system outperformed all of the human participants -we had a total score of 12,825 compared to the top human who had 12,810 (scoring details in appendix c). figure 5 shows our scores compared to the top and median human competitor on the 7 puzzles used in the competition. we also retrospectively evaluated the final bcs system as detailed in this paper (i.e., using our solver based on belief propagation and local search), and achieved a higher total score of 13,065. this corresponds to getting 6 out of the 7 puzzles perfect and 1 letter wrong on 1 puzzle. ## error analysis although our system obtains near-perfect accuracy on a wide variety of puzzles, we maintain that crosswords are not yet solved. in this section, we show that substantial headroom remains on qa accuracy and the handling of themed puzzles. ## related work past crossword solvers prior to our work, the three most successful automated crossword solvers were proverb, webcrow @xcite , and dr. standalone qa models for crosswords past work also evaluated qa techniques using crossword question-answer pairs. these include linear models @xcite , wordnet suggestions @xcite , and shallow neural networks @xcite ; we instead use state-of-the-art transformer models. ambiguous qa solving crossword puzzles requires answering ambiguous and underspecified clues while maintaining accurate estimates of model uncertainty. other qa tasks share similar challenges @xcite @xcite . crossword puzzles pose a novel challenge as they contain unique types of reasoning and linguistic phenomena such as wordplay. crossword themes we have largely ignored the presence of themes in crossword puzzles. themes range from simple topical similarities between answers to puzzles that must be filled in a circular pattern to be correct. while dr.fill @xcite has a variety of theme handling modules built into it, integrating themes into our probabilistic formulation remains as future work. cryptic crosswords we solve american-style crosswords that differ from british-style "cryptic" crosswords @xcite . cryptic crosswords involve a different set of conventions and challenges, e.g., more metalinguistic reasoning clues such as anagrams, and likely require different methods from those we propose. ## conclusion we have presented new methods for crossword solving based on neural question answering, structured decoding, and local search. our system outperforms even the best human solvers and can solve puzzles from a wide range of domains with perfect accuracy. despite this progress, some challenges remain in crossword solving, especially on the qa side, and we hope to spur future research in this direction by releasing a large dataset of question-answer pairs. in future work, we hope to design new ways of evaluating automated crossword solvers, including testing on puzzles that are designed to be difficult for computers and tasking models with puzzle generation.