File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Game Development and the fly likes Boggle game - Algorithms and data structures Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Game Development
Bookmark "Boggle game - Algorithms and data structures" Watch "Boggle game - Algorithms and data structures" New topic

Boggle game - Algorithms and data structures

Kemal Sokolovic

Joined: Jun 19, 2010
Posts: 825


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!

The quieter you are, the more you are able to hear.
Bert Bates

Joined: Oct 14, 2002
Posts: 8898
I'd love to hear more about your dictionary - is it open source, what form is it in, and so on...

Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Ben Wood
Ranch Hand

Joined: Aug 14, 2001
Posts: 342
I have used this one before, works quite well, I think it is Open...

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.

SCJP 1.4,
Kemal Sokolovic

Joined: Jun 19, 2010
Posts: 825

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
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
I haven't implemented one so I don't know the pitfalls, but a DAWG might be useful for this problem.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Phil Freihofner
Ranch Hand

Joined: Sep 01, 2010
Posts: 119
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.


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 I love this game!
Mich Robinson
Ranch Hand

Joined: Jun 28, 2009
Posts: 260
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.

Arcade : Alien Swarm
Board : Chess - Checkers - Connect 4 - Othello
I agree. Here's the link:
subject: Boggle game - Algorithms and data structures
It's not a secret anymore!