Solving crosswords with PROVERB

Abstract We attacked the problem of solving crossword puzzles by computer: Given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. PaOVEaB, the probabilistic cruciverbalist, separates the problem into two, more familiar subproblems: candidate generation and grid filling. In candidate generation, each clue is treated as a type of query to an information retrieval system, and relevant words of the correct length are returned along with confidence scores. In grid filling, the candidate words are fit into the puzzle grid to maximize an overall confidence score using a combination of ideas from belief network inference and constraint satisfaction. For our demonstration, we will have an interactive version of the candidate-generation process available via the web, and will also give people an opportunity to go head-tohead against PaOVERB in solving complete puzzles. Crossword puzzles have been an AI staple for many years, both as an example of the constraint satisfaction paradigm The architecture of the system consists primarily of a set of 30 "Expert Modules" responsible for suggesting solutions to the clues, and a "Solver" responsible for selecting candidate answers for each clue that fit together in the grid. To illustrate the candidate-generation process, we took the 70 clues from the crossword puzzle published in the New York Times, Thursday, October 10th, 1998. These clues were run through the expert modules and approximately 33 were solved with high confidence (in the top 10). After grid filling (combining crossing constraints with information from the clue), 62 clues were answered correctly. We examined the 33 well-solved clues to determine which expert modules contributed to the solution. These are described below. Modules come in several different types