Word-Find is a game where players compete to find the most unique words in a four by four grid of letters. Words are formed by starting at any letter, and moving from letter to adjacent letter until an English word is spelled out. You can move up, down, left, or right, or diagonally. A single letter tile may only be used once in forming a word. Any English word longer than two letters is acceptable as long as it isn't a proper noun.
Words are scored based on the length of the word:
The dictionary the computer uses is from a word list I found online. It's called the Twelve Dictionaries list from wordlist.sourceforge.net (which is a great resource maintained by Kevin Atkinson.) It contains a broad set of words (around 790KB of words) and includes inflections. I have tried some other dictionaries but this one seems to strike a nice balance between having lots of words but not having too many esoteric words that aren't in common use. Click here to see the dictionary.
This site lets you play Word-Find against the computer. The computer uses the dictionary to calculate how many possible words can be formed, and you can try to complete as many of the words as possible. Depending on the board, getting even 50% of the words the computer finds is pretty hard to do. Click here to play.
Ever wonder what the highest possible scoring Word-Find board is? Well I don't know what the highest scoring possible board is, but here are some of the highest scoring boards ever found:
If you want to become famous by finding the highest scoring Word-Find board known to humankind, then click here to let your computer waste some CPU time searching.
The Word-Find search works by starting with a quasi-random board, then trying to change it around so that it results in a higher score. It attempts to swap dice and rotate dice, and sometimes does multiple sequences of these changes. After each sequence of changes, it tests the new board to determine if the score is higher. Note that the simulation models the dice in the actual Boggle game, so you can be sure any board it produces can be recreated in real life using your Boggle set.
This "Best Word-Find Board" problem is a classic high-dimension optimization problem. The number of possible boards is immense - (16! * 616) different arrangement of dice. Of course many of the boards have the same score, because they're equivalent (consider a board rotated 90 degrees, for example.) It still doesn't change the fact that trying to brute-force the highest scoring Word-Find board is very computationally intensive.
The scheme this site uses to find high scoring boards is called simulated annealing. The idea is to try to minimize an energy function for a high dimension system. For this system we use Score(board)-1 as the energy function. Higher scoring boards produce lower values for the energy function. We try to make small changes that reduce the energy in the system in hopes that we arrive at a local minimum for the energy function. However this technique can't tell us anything about whether or not we've found a global minimum, which in our case would correspond to the highest scoring Word-Find board.