Cracking Crosswords: The Computer ChallengeReasoning, Action and Interaction in AI Theories and Systems

Crosswords is over 90 years old, yet it is still one of the most popular puzzles around the world. It is in fact a linguistic game which requires a wide knowledge in different domains and the ability to crack enigmatic clues, that are often regarded as inherent human capabilities. Unlike chess, crossword solving does not require strong skills for the actuation of strategic plans, but the linguistic specifications is in itself a source of enormous difficulty for machines. This paper discusses the problem of automatic crossword solving with special emphasis to the WebCrow project carried out at the University of Siena. After a brief historical description of the evolution of crosswords, the paper gives a formalization of the main problems to be faced and provides a number of relevant architectural issues behind cracking crosswords. In particular, it is claimed that the Web is likely to be the most important source for the development of challenging programs based on clue answering, a sort of question answering mechanism in which the machine is expected to return candidate word solutions. © 2006 Springer-Verlag Berlin/Heidelberg.