Boggle game - Algorithms and data structures

[Kemal Sokolovic]

Howdy!

I am now working on a simple Boggle game. The problem is with searching letters on board to find as many words that are 3 or more letters long.
I have an English dictionary containing 60000+ words, so searching it brute force is not the best solution. Also, searching a 6x6 board the similar way, by checking all possibilities would make application slow as hell! So, any recommendations would be great!

I'm not looking for a code as a solution, just for some advices about algorithms and data structures I should use, to get the job done.
Thanks in advance!

[Bert Bates]

I'd love to hear more about your dictionary - is it open source, what form is it in, and so on...

[Ben Wood]

I have used this one before, works quite well, I think it is Open...

http://sourceforge.net/projects/jazzy/

I haven't used the API on this for a while so I don't remember if it provides any search/indexing stuff.

If not, I think you will need to find a way of indexing all of the entries in the dictionary using some form of tree structure perhaps, so that for a given sequence of letters you can quickly drill down through the dictionary entries to focus on possible matches, rather than brute-force searching all dictionary entries until you find a match.

http://en.wikipedia.org/wiki/Tree_data_structure

[Kemal Sokolovic]

Thanks for replies!
I think I could handle it with a proper data structure to store a dictionary. But I don't have any idea how to implement searching across board.
So, i have (for example, 4x4) matrix of letters. What kind of algorithm should I implement to find as many 3+ letters words there?

[Garrett Rowe]

I haven't implemented one so I don't know the pitfalls, but a DAWG might be useful for this problem.

[Phil Freihofner]

Wow! Thanks for the dictionary link. I have a game I've been working on that I originally wrote in VBA (on top of MS Access) and used the microsoft dictionary tools. It was the only language I knew, but like, a pointless endeavor since there is no way to monetize something that requires a person own an expensive database application in order to play it. So now I'm learning Java and will redo the project.

OK, back to the question about the searches.

The only thing I can think of is to do an exhaustive tree search through the grid. To do the search, each square should be an object that has a hardcoded list of neighbors that can be searched progressively. (The list of neighbors should have a FAST iterator or use a very efficient For:Each.) Each square will also have to have a boolean to "mark" it as part of the current word search so that you don't back track onto yourself. I'd make each list of "neighbors" as similar as possible, for example, starting at 12:00 and going clockwise. With each step into the tree you have to look up the word. As long as you are still forming a word, you continue with the tree. As soon as you hit a letter that makes your string something that is not either a word or not a part of a word, you backtrack and continue clockwise to the next neighbor. I suspect that you'll want to go depth-first in this situation.

Example:

STAR (is a word, continue) START (is a word, continue) STARTL (is part of a word, continue) STARTLP (not a word, backtrack)
Note: the search through the dictionary on this branch is forward only, and the words are close together. So there are undoubtably some efficiencies there! For example, after STARTLE I have STARVATION, with nothing inbetween, but LP is inbetween LE & V, so therefore STARTLP can NOT be a word or part of a longer word.

Anyway, the main point is that if you start with the grid and look up possible words, I think you'll have a lot less looking up to do than if you start with the dictionary and try to find each word of it in the grid.

Have you played at http://www.wordsplay.net? I love this game!

[Mich Robinson]

Can't you just generate a bunch of letter sequences from the board.
We'll call these potential words.
Remove any potential words that don't contain a vowel.
Remove potential words that have a Q not followed by a U.
You could then order these potential words so that 3 letter words with 2 constants and a vowel in the middle come first.
4 letter combinations come after 3 letter combinations.
Put words containing Z, X, Q, V etc at the very end.

Start a timer and just look for each potential word in the dictionary until the time runs out.
To make the game more difficult just increase the time.