[Help] Word game algorithm?

[blkhwks19]

Im looking to build a word game similar to boggle. Basically I have random letters appear in a 4x4 grid. I need to know how many words can be spelled using that specific layout of letters. So my question has 2 parts:

1) Where can I get a dictionary of words to check against for use in a game like this? Ive heard of some people creating their own, but Im not looking to compile a list of a handful of words, Im looking to compare against every word in the english language. Like a scrabble dictionary or something similar.

2) Once I have the dictionary, how do I go about writing an algorithm that will first create a grid of random letters, and then analyze that grid and scan it for all the possible words that are in the dictionary?

Hopefully that makes sense. Im just making this game for giggles and if anything it would be good practice and give me a good learning experience. Especially if someone can shed some light on algorithms.

Any advice would be really appreciated! Thanks!

[blkhwks19]

Anyone at all have any advice or suggestions for how to go about approaching this?

[ImprisonedPride]

1) http://www.mieliestronk.com/wordlist.html <- will get you started, 58000 words. You'll need to convert it to an array or parse the list from a text file yourself.

2) You're looking at the process backwards. What you should do is denote a difficulty based on a length of a word. From there, sub-categorize the difficulties and select a random yet acceptable word and place it on the board. Next, grab a random letter from that word and decide where in the new word that letter will be placed. Scan the parsed dictionary for words matching both your preferred difficulty and/or space requirement. If it does not, choose a new letter. When no more space remains, fill the remaining empty spaces with random consonants (rather than vowels to avoid unintended words). That should be enough to get you started on a working prototype.

[slight]

I did something similar a while ago, forget now where I got my wordlists from, there are many of them, and I think in the end I had to splice a few together to get it just right.

Your second question is a bit more difficult. For 16 random letters there is an absolutely huge number of permutations to check (20922789888000 combinations just for 16 letter words) so basically... don't do it, it will take minutes or maybe hours to calculate.

If all you wanted to do however was check a handful of words (eg 10 x 4 letter words going across, down and diagonal) then your best bet as far as speed vs memory goes is to do a binary search. I found I could check several hundred strings per frame without hitching 30fps, it could maybe do more, I didn't need that many checks.

It takes a long time to compile the wordlist, you might want to keep it in a separate swf. I actually have one of these as a swf which you are welcome to use, shoot me a PM if you want it, it just has a wordlist and the binary search, though it is old and in AS2. From the main program it has only two functions: isWord(string) which returns a boolean and randomWord() which returns any one word from the dictionary.