 [Nature Federica Castellani]Multilingual algorithm uses web to find words. 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. 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." |
