Crossword Puzzles

AITopics > Games & Puzzles > Crossword Puzzles

"Crossword puzzles...require of the solver both an extensive knowledge of language, history and popular culture, and a search over possible answers to find a set that fits in the grid. This dual task, of answering natural language questions requiring shallow, broad knowledge, and of searching for an optimal set of answers for the grid, makes these puzzles an interesting challenge for artificial intelligence." - from PROVERB

Introductory Readings

Rise of the crossword robots: Computers vs. humans hits the next frontier by Ben Zimmer. , Boston Globe (March 11, 2012). "Unlike the other assembled crossword experts, Dr. Fill is not human. The Doctor is a crossword-solving program, and will be running on the notebook computer of Matt Ginsberg, a software engineer from Eugene, Ore. When the bell rings and humans start solving the first of seven championship puzzles, Ginsberg will hit <enter> and Dr. Fill will get to work, in an attempt to achieve the highest score in the tournament."

Proverb: The probabilistic cruciverbalist (AAAI–99 Outstanding Paper Award). By Greg A. Keim, Noam Shazeer, Michael L. Littman, Sushant Agarwal, Catherine M. Cheves, Joseph Fitzgerald, Jason Grosland, Fan Jiang, Shannon Pollard, and Karl Weinmeister. 1999. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 710-717. Menlo Park, Calif.: AAAI Press. Also available in several formats from CiteSeer.

• 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. In our system, 'expert modules' specialize in solving specific types of clues, drawing on ideas from information retrieval, database search, and machine learning. Each expert module generates a (possibly empty) candidate list for each clue, and the lists are merged together and placed into the grid by a centralized solver. We used a probabilistic representation throughout the system as a common interchange language between subsystems and to drive the search for an optimal solution. Proverb, the complete system, averages 95.3% words correct and 98.1% letters correct in under 15 minutes per puzzle on a sample of 370 puzzles taken from the New York Times and several other puzzle sources. This corresponds to missing roughly 3 words or 4 letters on a daily 15x15 puzzle, making Proverb a better-than-average cruciverbalist (crossword solver)."

Crossword software thrashes human challengers. By Tom Simonite. NewScientist.com news (August 31, 2006). "A crossword-solving computer program yesterday triumphed in a competition against humans. Two versions of the program, called WebCrow, finished first and second in a competition that gave bilingual entrants 90 minutes to work on five different crosswords in Italian and English. The competition took place in Riva del Garda, Italy, as part of the European Conference on Artificial Intelligence."

• Visit the WebCrow site where, among other things, you can see the ECAI-06 results, find out "How it works," and access several papers and documents.
• Also see:
  • WebCrow - A Web-Based System for Crossword Solving. By Marco Ernandes, Giovanni Angelini, and Marco Gori. 2005. In Proceedings of the Twentieh National Conference on Artificial Intelligence, 1412 - __. Menlo Park, Calif.: AAAI Press."Language games represent one of the most fascinating challenges of research in artificial intelligence. In this paper we give an overview of WebCrow, a system that tackles crosswords using the Web as a knowledge base. This appears to be a novel approach with respect to the available literature. It is also the first solver for non- English crosswords and it has been designed to be potentially multilingual. Although WebCrow has been implemented only in a preliminary version, it already displays very interesting results reaching the performance of a human beginner: crosswords that are 'easy' for expert humans are solved, within competition time limits, with 80 percent of correct words and over 90 percent of correct letters."
  • I'm Puzzled. Editor's Eye blog by Jon Erickson. Dr. Dobb's Portal (September 5, 2006). "I like to tell myself that I'm pretty good at times, but I admit I'm no where as good as WebCrow, a computer program that took on--and soundly whipped--dozens of human competitors at last month's European Conference on Artificial Intelligence. ... According to the authors, problems like solving crosswords from clues have been defined as AI-complete and are extremely challenging for machines since there is no closed-world assumption and they require human-level knowledge. Interestingly, for the first time since AI's kick-off, there is a first nucleus of technology, such as search engines, information retrieval and machine learning techniques, that enable computers to enfold with semantics real-life concepts. The goal of WebCrow's authors is to design a software system whose major assumption is to attack crosswords making use of the Web as its primary source of knowledge."

Constraint Satisfaction Problems: Definition of CSP - A simple example: the crossword puzzle. From Marc Torrens's 1997 thesis: An application using the Java Constraint Library: The Air Travel Planning system. Follow the links to find out what crossword puzzles have to do with CSP's.

Crossword. This program from Scott Roy, and available from the CMU Artificial Intelligence Repository, "allows you to create blank crossword puzzle frames and then have the computer fill them with words from a chosen dictionary....The program is intended to provide a testing ground for different search algorithms."

General Readings

A probabilistic approach to solving crossword puzzles. Michael L. Littman, Greg A. Keim, and Noam Shazeer. Artificial Intelligence (January 2002Volume: 134, Issue: 1-2). Abstract excerpt: "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. After an analysis of a large collection of puzzles, we decided to use an open architecture in which independent programs specialize in solving specific types of clues, drawing on ideas from information retrieval, database search, and machine learning."

Solving Crosswords with Proverb. By Michael L. Littman, Greg A. Keim, and Noam M. Shazeer, Duke University. 1999. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 914 - . Menlo Park, Calif.: AAAI Press. "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. Proverb , 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-to- head against Proverb in solving complete puzzles."

Completing Latin Squares. By Ivar Peterson (2000). Science News Online. (Week of May 6, 2000; Vol. 157, No. 19). A wonderful introduction to Latin squares and quasigroup completion problems.

Solving Crossword Puzzles as Probabilistic Constraint Satisfaction. By Noam M. Shazeer, Michael L. Littman, and Greg A. Keim, Duke University. 1999. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 156 - . Menlo Park, Calif.: AAAI Press. "Crossword puzzle solving is a classic constraint satisfaction problem, but, when solving a real puzzle, the mapping from clues to variable domains is not perfectly crisp. At best, clues induce a probability distribution over viable targets, which must somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, we provide a formal model of constraint satisfaction with probabilistic preferences on variable values. Two natural optimization problems are defined for this model: maximizing the probability of a correct solution, and maximizing the number of correct words (variable values) in the solution. We provide an efficient iterative approximation for the latter based on dynamic programming and present very encouraging results on a collection of real and artificial crossword puzzles."

Related Resources

Crossword Links. From the American Crossword Puzzle Tournament.

Crossword Maestro. "[T]he world's first expert system for solving cryptic and non-cryptic crosswords. It's major breakthrough in Artificial Intelligence. Crossword Maestro is not just an anagram solver, thesaurus and letter pattern searcher, nor is it solely an electronic crossword dictionary, although it can easily do any of these tasks. It's better thought of as a highly intelligent crossword mentor which, once purchased, is on hand twenty-four hours a day to suggest answers to clues; explain how a given cryptic clue works; challenge you to a crossword solving match; finish off your attempt at solving the crossword in your daily newspaper; or even set about solving it completely for you."

WebCrow, the WEB CROssWord solver: solving crosswords using the Web. (Also see related materials above.)

Related AITopics Pages

• Bridge
• Checkers
• Chess
• Go
• Othello
• Poker
• Scrabble
• Traveling Salesperson & NP-Complete
• More Games & Puzzles
• ...and check out our AI crossword puzzles

Other References Offline

Littman, Michael L. 1999. Computers and Language Games. IEEE Intelligent Systems. 14 (6): pp. 17 - 18.