Unlike most games and puzzles attacked by the artificial intelligence community, crossword puzzles have no formal definition. Instead, of combinatorial search, they derive their challenge from the flexibility and ambiguity of natural language. To explore computational methods for addressing these issues, we created an automated crossword solver called Proverb. Proverb draws on powerful ideas from information retrieval, data mining, and statistical natural language processing to suggest candidate answers to the clues in a standard crossword puzzle. The problem of fitting the resulting candidate into the grid is then viewed as a type of probabilistic constraint satisfication problem, and Proverb searches for a solution that optimizes the expected number of correct answers. On a set of 370 puzzles chosen from seven different publishers, Proverb averaged over 95% words correct per puzzle, putting it approximately at the level of an advanced intermediate human solver.
Joint work with Greg A. Keim, Noam Shazeer, and the Duke Crossword Puzzle Seminar.
For the colloquium series schedule, see the UMD Computational Linguistics Colloquium Series web page at http://umiacs.umd.edu/~resnik/cl_colloquium/. If you are interested in meeting with the speaker, please contact Philip Resnik (resnik@umiacs.umd.edu).