Automated Crossword Solving

• URL: http://arxiv.org/abs/2205.09665v1
• Date: Thu, 19 May 2022 16:28:44 GMT
• Title: Automated Crossword Solving
• Authors: Eric Wallace, Nicholas Tomlin, Albert Xu, Kevin Yang, Eshaan Pathak, Matthew Ginsberg, Dan Klein
• Abstract summary: Our system improves exact puzzle accuracy from 57% to 82% on crosswords from The New York Times. Our system also won first place at the top human crossword tournament.
• Score: 38.36920665368784
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Proving that Cryptic Crossword Clue Answers are Correct [0.18416014644193066]
  We show that it is possible to distinguish between correct answers and almost-correct ones based upon whether the wordplay works' We show that it is possible to distinguish between correct answers and almost-correct ones based upon whether the wordplay works'
  arXiv  Detail & Related papers  (2024-07-11T19:13:16Z)
• Language Models are Crossword Solvers [1.53744306569115]
  We tackle the challenge of solving crosswords with Large Language Models (LLMs) We demonstrate that the current generation of state-of-the art (SoTA) language models show significant competence at deciphering cryptic crossword clues. We also develop a search algorithm that builds off this performance to tackle the problem of solving full crossword grids with LLMs.
  arXiv  Detail & Related papers  (2024-06-13T12:29:27Z)
• The WebCrow French Crossword Solver [6.758790625418374]
  We extend WebCrow, an automatic crossword solver, to French, making it the first program for crossword solving in the French language. To cope with the lack of a large repository of clue-answer crossword data, WebCrow exploits multiple modules, called experts, that retrieve candidate answers from heterogeneous resources. We compared WebCrow's performance against humans in two different challenges. Despite the limited amount of past crosswords, French WebCrow was competitive, actually outperforming humans in terms of speed and accuracy.
  arXiv  Detail & Related papers  (2023-11-27T08:45:31Z)
• Solving Witness-type Triangle Puzzles Faster with an Automatically Learned Human-Explainable Predicate [0.29005223064604074]
  We develop a search-based artificial intelligence puzzle solver for The Witness game. We learn a human-explainable predicate that predicts whether a partial path to a Witness-type puzzle is not completable to a solution path. We prove a key property of the learned predicate which allows us to use it for pruning successor states in search.
  arXiv  Detail & Related papers  (2023-08-04T18:52:18Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• Automated Graph Genetic Algorithm based Puzzle Validation for Faster Game Desig [69.02688684221265]
  This paper presents an evolutionary algorithm, empowered by expert-knowledge informeds, for solving logical puzzles in video games efficiently. We discuss multiple variations of hybrid genetic approaches for constraint satisfaction problems that allow us to find a diverse set of near-optimal solutions for puzzles.
  arXiv  Detail & Related papers  (2023-02-17T18:15:33Z)
• Video Anomaly Detection by Solving Decoupled Spatio-Temporal Jigsaw Puzzles [67.39567701983357]
  Video Anomaly Detection (VAD) is an important topic in computer vision. Motivated by the recent advances in self-supervised learning, this paper addresses VAD by solving an intuitive yet challenging pretext task. Our method outperforms state-of-the-art counterparts on three public benchmarks.
  arXiv  Detail & Related papers  (2022-07-20T19:49:32Z)
• Down and Across: Introducing Crossword-Solving as a New NLP Benchmark [11.194615436370507]
  We release the specification of a corpus of crossword puzzles collected from the New York Times daily crossword spanning 25 years. These puzzles include a diverse set of clues: historic, factual, word meaning, synonyms/antonyms, fill-in-the-blank, abbreviations, prefixes/suffixes, wordplay, and cross-lingual.
  arXiv  Detail & Related papers  (2022-05-20T21:16:44Z)
• The NTT DCASE2020 Challenge Task 6 system: Automated Audio Captioning with Keywords and Sentence Length Estimation [49.41766997393417]
  This report describes the system participating to the Detection and Classification of Acoustic Scenes and Events (DCASE) 2020 Challenge, Task 6. Our submission focuses on solving two indeterminacy problems in automated audio captioning: word selection indeterminacy and sentence length indeterminacy. We simultaneously solve the main caption generation and sub indeterminacy problems by estimating keywords and sentence length through multi-task learning.
  arXiv  Detail & Related papers  (2020-07-01T04:26:27Z)
• PuzzLing Machines: A Challenge on Learning From Small Data [64.513459448362]
  We introduce a challenge on learning from small data, PuzzLing Machines, which consists of Rosetta Stone puzzles from Linguistic Olympiads for high school students. Our challenge contains around 100 puzzles covering a wide range of linguistic phenomena from 81 languages. We show that both simple statistical algorithms and state-of-the-art deep neural models perform inadequately on this challenge, as expected.
  arXiv  Detail & Related papers  (2020-04-27T20:34:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.