Jump to content
  • Advertisement
Sign in to follow this  
paulbird

crossword solving

This topic is 4864 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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 :)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
i think this guy just wants to win £20 a week on the times sunday crossword!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!