Angry Words: An Automated Crossword-Puzzle Solver
Advisor: David Liben-Nowell
Crossword puzzles are riddled with facts about the world (Giant
slugger Mel; The shallowest great lake; Computer that
debuted in 1946), basic "language use" knowledge (Happy
as ; Word after labor or
arbor), not to mention basic dictionary knowledge (synonyms), plus
bad puns and vicious wordplay. Solving crosswords feels like a
uniquely human endeavor—but then again, so did chess (Deep Blue)
and Jeopardy! (Watson). In the most recent American Crossword
Puzzle Tournament, a computer entrant
named Dr. Fill,
written by Dr. Matt Ginsberg, placed in the top tier of crossword
solvers in the world.
Solving puzzles is hard: one needs to mix, on one hand, various
knowledge sources that generate guesses about answers with, on the
other, the constraints formed by the crossing words. Even the best
solvers maintain competing hypotheses for a single word; they select
among these hypotheses using the crossing entries (perhaps propagating
information from far away in the grid).
II. The Project
For this project, you will implement an automated software system
to solve crossword puzzles. A rough outline of your work on this
project will be something like the following:
- Research the existing crossword-solving programs and
the Jeopardy!-playing system Watson.
- Design an overall system architecture. How will you collect
knowledge that may answer clues? How will you combine guesses on
individual answers into a solution for the puzzle as a whole?
- Develop a platform for world- and language-knowledge facts that
allows you to suck in facts about the world (from a dictionary or
Wordnet or an atlas or the web or whatever) and proposes possible
answers to a given clue, with some measure of confidence.
- Develop a algorithm to fill a grid. Given proposed possible
answers, with confidences, how do you fill the grid?
- Develop a test plan. How will you identify "what went wrong" when
you program gets stuck? How will you iteratively improve your fact
platform or your algorithm?
Existing crossword-solving software:
- Matthew L. Ginsberg.
Crosswords and an Implemented Solver for Singly Weighted CSPs.
Journal of Artificial Intelligence Research, 2011.
Michael L. Littman, Greg A. Keim, Noam M. Shazeer.
A probabilistic approach to solving crossword
puzzles, Artificial Intelligence, 2002.
Marco Ernandes, Giovanni Angelini, Marco Gori.
a WEB-based system for CROssWord solving
David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya A. Kalyanpur, Adam Lally, J. William Murdock, Eric Nyberg, John Prager, Nico Schlaefer, and Chris Welty.
Watson: An Overview of the DeepQA Project.
AI Magazine, 2010.