Crossword
Puzzles
(a subtopic of Games
& 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 |
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)."
Program cracks crosswords. By Federica Castellani. news@ nature.com (October 4, 2004). "It's a boon for puzzle addicts and a small leap forward for artificial intelligence: a computer program that can solve crosswords in any language. The program, called Web Crow, reads crossword clues, surfs the web for the answers and fits them into the puzzle. Computer engineers Marco Gori and Marco Ernandes at the University of Siena in Italy say a prototype should be available by the end of the year. ... Gori says that the algorithms developed for Web Crow could find a use elsewhere in artificial intelligence. For example, the part of the program that creates the queries could be used to develop software that can automatically extract useful information from the web."
- 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."
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."
Thesis: Design and Implementation of Crossword Compilation Programs Using Sequential Approaches. By Sik Cambon Jensen (1997).
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."
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."
- Overview
- Bridge
- Checkers
- Chess
- Go
- Othello
- Poker
- Scrabble
- Traveling Salesperson & NP-Complete
- More Games & Puzzles
Littman, Michael L. 1999. Computers and Language Games. IEEE Intelligent Systems. 14 (6): pp. 17 - 18.