You can also download all the source code and dictionaries here.
O A A N E T R I I H K R I F L VThe 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 rateIf 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!
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 fitI 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.''
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.
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