 |  | 
Published online: 04 October 2004; | doi:10.1038/news041004-2
Program cracks crosswords Federica Castellani Multilingual algorithm uses web to find words.
| Surf the web to find the answer. © Punchstock |
|
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.
The
world's first crossword-solving computer program was developed in 1999
by researchers at Duke University in Durham, North Carolina. Called
Proverb, it uses a variety of databases to solve puzzles, but only in
English. Web Crow can solve crosswords in any language.
 The idea is not to spoil the enjoyment of players.  |
Marco Gori
University of Siena, Italy |
|
| | |
Web
Crow works in two phases. In the first, it analyses the crossword clue
and turns it into a simple query. Then it plugs the query into the
internet search engine Google and uses a certainty score to rank the
possible solutions in a candidate list. "One time in ten, the correct
word is at the top of the candidate list," says Gori.
In
the second phase, the program uses an algorithm to figure out which
candidate words provide the best fit for the grid as a whole.
Real-world solutions
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.
And
the part of the program that figures out how best to fit all the
candidate words into the crossword grid might find a use working out
the best combination of other pieces of information, such as course
schedules or staff shifts.
The
program could give most crossword experts a run for their money,
according to the researchers. "It may not be able to solve the most
difficult clues all the time," says Gori, but it can solve most in most
languages. "What experts can do that, even in two languages?" But, he
adds, "the idea is not to spoil the enjoyment of players."
| |
Story from news@nature.com:
http://news.nature.com//news/2004/041004/041004-2.html |
| |
|