The Boggle Solver

New -- Now you can use the online boggle solver to solve boggle boards using your web browser!

You can also download all the source code and dictionaries here.

The Problem

On the evening of December 19, 1995, I stumbled across the #boggle channel on IRC. The channel has an automated program (affectionately called ``Boggy''), written by Kenrick Mock, that lets people play competitive Boggle against each other. In Boggle, you typically get a 4x4 matrix of random letters, like this:
	O A A N
	E T R I
	I H K R
	I F L V
The object of the game is to find as many English words as possible in the letter matrix within three minutes. Each word must be made up of a sequence of adjacent or diagonal letters in the matrix, but without any repeated letter-positions. For example, in the above matrix, "oat" is legal (starting from the top left), as is "rain" (starting from the R in the second row), and "rate" (starting from the same R).

On the #boggle channel, the object of the game is to find as many of these words as possible, before anyone else does. You communicate with the Boggle bot (short for ``robot'') by typing the word "bog", followed by a word, like this:

bog oat
bog rain
bog rate
If you come up with a valid word in the matrix before anyone else, the bot gives you points. Longer words score more points. Whoever has the most points after three minutes wins the game.

Well, it turns out that quite a few people spend quite a bit of time playing IRC Boggle, and a lot of them are quite good. I, on the other hand, had never played before, and was terrible. Typically I'd only be able to come up with a dozen or so words in three minutes while other people on the channel were coming up with 50!

The Solution

Now, I'm not a sore loser normally, but after 10 games I started getting a little tired of losing so terribly. I should have given up. But instead, I realized that it would probably be pretty easy to write a simple program that would find words in the matrix faster than any human possibly could. In a little over an hour, I whipped up a program that did exactly that. Running the program on the above matrix, for example, gives the following output almost instantly:
bog oat
bog oath
bog oar
bog ate
bog art
bog artie
bog ark
bog ani
bog air
bog nat
bog nato
bog nate
bog nair
bog eat
bog ear
bog earn
bog earth
bog eta
bog toe
bog tao
bog tar
bog tara
bog tan
bog tea
bog tear
bog tehran
bog train
bog tie
bog the
bog thea
bog rae
bog rat
bog rata
bog rate
bog ran
bog rain
bog rna
bog rhea
bog ian
bog ira
bog irate
bog iran
bog irk
bog ito
bog heat
bog hear
bog heart
bog hit
bog kin
bog fit
I went back to the #boggle channel with my IRC client in one window and my Boggle-solver program in another. When the game started, I just copied the board out of the IRC window and pasted it into the Boggle-solver window. The solver printed a huge list of words which I then copied and pasted back into the IRC window, causing me to win the game by an absurd margin and earn both praise and suspicious comments from the players who had been severely beating me an hour earlier. Score one for Hopkins Computer Science education!!

On some boards this solver would come up with hundreds of words; far more words than I could even paste into the IRC window within three minutes. After a few games, it stopped being fun, and I felt like I was just being a jerk by ruining the game for everyone else, so I left. I felt guilty about it later, but my friend Josh summed it up best recently when he said: ``There are worse things in life than making a mockery of an online Boggle game.''

How does the solver work?

It's not too complicated, really -- the Boggle solver is only 150 lines of C code. The solver enumerates every possible combination of letters in the board (up to a certain maximum length), and looks up each letter combination in the dictionary to see if it's a legal word or not. If it's a legal word, the solver prints it, after making sure that the same word hasn't already been printed. The checking for duplicates is useful because there is often more than one way to form the same word on a Boggle board.

My solver uses a depth-first search to generate the letter combinations, with a bound on the maximum depth, and a binary search to quickly look up each letter combination in the dictionary to see if it's a word or not. On a Pentium 120 running Linux, it takes my solver a mere 5 seconds to solve a 4x4 Boggle board when searching for words of a maximum length of 8 letters! Of course, there's nothing particularly innovative about my Boggle solver; after all, the Boggle bot that runs the games on the #boggle channel almost certainly uses the same algorithm (or a similar one) to referee the games.

The only weakness of my solver is that it's only as good as the dictionary you give it. There are a lot of legal Boggle words that aren't in the UNIX dictionary, so my solver doesn't find them. If only I could get my hands on an electronic Scrabble dictionary... naah, I'm already enough of a jerk.

Warning

As with most programs written in an hour, this program is a hack. Like all hacks, this program has no user interface, documentation, or comments in the code, and does very little error checking. But that's what makes it beautiful!

And remember, kiddies: a CS education gives you power. That power can be used both for good and for evil. This program is an example of the latter. However, I did recently discover that it earned me a point on Question 109 of the Hacker Test.


Back to my software page
Back to my home page

Jeremy Elson
Last updated: 1 June 1998