Challenge: ============ How would you go about writing a program that solves crossword puzzles? For example I think you would need at least these things (in no particular order): To be able to search the interent such as with Google's API (although this only allows 1000 searches a day). A word net database which links words such as "finger"-->part of-->"hand". "cat"---type of--->animal. Such as WordNet or WordWeb from the internet. Databases such a dictionaries, thesaurus, encylopedia. Syntax and grammar analyser which you'd probably write yourself which is specifically designed to interpret clues. For cryptic clues you would also need a database of how to solve cryptic puzzles such as which words indicate anagrams. Then the program would go through each clue to see what possible words might be answers to the clues. Next it would simply be a case of fitting in as many as will go. Then maybe reevaluating the final clues to fit with the letters you have got. Any other ideas?

I think you're on the right track with the dictionary thesaurus thing. Also some type of keyword matching through Google could be usefull, perhaps if you search for the clue you could weight the words from the results based on how many times it was in the search results.

After all that at a certain point with the dictionary you could brute force the rest of the way without much trouble, though that might be a bit like cheating :)

1. Find all words that fit.
2. Use the words that fit in a constraints satifaction problem to 'solve' the crossword. (this should take < 1 second probably).
3. If more then one solution exists, google the question and look for the possible words in the answer.

From,
Nice coder

Quote: Original post by Nice Coder
1. Find all words that fit.
2. Use the words that fit in a constraints satifaction problem to 'solve' the crossword. (this should take < 1 second probably).
3. If more then one solution exists, google the question and look for the possible words in the answer.

From,
Nice coder

This appears to be the best solution to me as well. However, I'd propose combining steps 2 and 3, simply because I've actually written a crossword solving program using constraint satisfaction algorithms and it literally takes days on a typical computer using a 33,000 word dictionary to solve the constraint problem on a crossword puzzle taken from the newspaper -- LOTS of possible solutions exist (and to solve a typical crossword would take much more than 33,000 words). Hence, I propose a word selection system that gives favor to words which are able to be found related via Google (although admittedly this is somewhat ambiguous) and to attempt these first. A human would still probably have to sit down and parse through many many solutions manually after a great deal of time is spent solving the constraint problem.

What got me thinking about this was that instead of Artificial Intelligence maybe what people really should be creating is Artificial Intellectuals. One of these robots should be able to:

1.Do the Times Crossword.
2.Read a book and sum it up in a witty remark.
3.Watch TV and sneer at it how dumbed down it all is.
4.Smoke a Pipe.

I think the technology is almost here for such an achievement.

Quote: Original post by paulbird
What got me thinking about this was that instead of Artificial Intelligence maybe what people really should be creating is Artificial Intellectuals. One of these robots should be able to:

1.Do the Times Crossword.
2.Read a book and sum it up in a witty remark.
3.Watch TV and sneer at it how dumbed down it all is.
4.Smoke a Pipe.

I think the technology is almost here for such an achievement.

It is much harder to make an intelligent being than to make an intellectual. [grin]

i think this guy just wants to win £20 a week on the times sunday crossword!