# BoggleTM - source code

This is a resource of the wordgame-programmers@egroups.com mailing list.

Click to subscribe to wordgame-programmers

Here is a wide selection of algorithms for finding the words in a boggle layout. Generally these are a depth-first search, hopefully with pruning on the fly. Some of these are very fast and others are very slow.

We also have some code for generating Boggle layouts - doing it randomly is trivial, but generating a layout in order to maximise the number of words found, or to fit specific words into the board, is far from trivial. We have code examples here which generate dense Boggle boards using techniques such as genetic algorithms and simulated annealing. This is not a problem that can be solved by brute force. (An ongoing conversation on this theme can be found at StackExchange)

Note these other games above (Traverse and Word factory) which are scored in a manner similar to Boggle, for which the software below would be just as relevant.

Visit the Official Hasbro Boggle Site

There are many web sites on the net which allow you to play Boggle interactively. If that's what you're looking for, go use Alta Vista or any of the search engines to find them on your own. Some sites offer a game called "Tangleword" which seems to me almost identical to Boggle. There are no downloadable executables here and no interactive web games. What we have on our archive are only the sources of computer programs for academic study. Read the rules to Boggle if you're not familiar with the game.

These are the programs which create densely-populated Boggle layouts
• goetz_boggle/
Phil Goetz's genetic algorithm. Challenge: can you beat Phil's code's record for a dense boggle board?
(Inspired by Ed & Jennifer's Boggle Puzzle)
• Chuong (Tom) Do's code to generate dense boggle grids
The implemented algorithm can be summarized as employing a few basic strategies:
2. Perturb each of the N random configurations in one of the ways described below. To better determine perturbation success, the program keeps track of the percentage of times that a particular perturbation type given a particular parameter succeeds in improving the board configuration. Choice of the perturbation to be performed on a board is picked randomly among the possible perturbations and parameters using the weighting based on past performance.
1. Change k randomly selected letters on the board.
2. Swap k randomly selected adjacent pairs of letters.
3. Swap k randomly selected pairs of letters.
4. Rotate the board k1 positions vertically and k2 positions horizontally.
3. Concatenate the original list of N configurations with the new list of N perturbed configurations, sort by board score (computed by finding total Boggle® score possible for the board, which is not necessarily the same as the maximum number of words), and keep the N best configurations. Go to step 2 and repeat.

• potm/inverse-boggle/
Programmer of the Month competition entries. Code for "snakepit" (also a genetic algorithm) and descriptions of the other entrants.
• Mactech Challenge/Solution
Mactech refused permission for us to put usable copies of their files on this site, so you will have to extract them from the pages above. (View the source - copying from the HTML display messes up). Ernst Munter (a prolific algorithm creator and code writer) has an entry based on simulated annealing. It's interesting to compare against a genetic algorithm.
• Professor Guy Schafer's Inverse Boggle
• Justin's Thesis
Here is a pdf file of the PostScript document above. Skip to the foot of page 104 (pdf numbering) or 102 (internal document numbering) for the bit that's relevant to Boggle. His best boggle layout is:
RSTCS
DEIAE
GNLRP
EATES
MSSID
• Word Grid
The "Word Grid" program in the Mactech competitons is a special subset of the above problem. It attempts to fit a specific string into the smallest space. Their example is: How much wood would a woodchuck chuck if a woodchuck could chuck wood?
HWMU
OOCH
UDWK
LAFI

These programs solve boggle puzzles or play boggle interactively.
• Neil Pearce's Boggle
• bagosrc/
I haven't tried the executable, but the source looks well written and shows how to write a Windows GUI program, as well as handling the basic word-finding engine.
• boggle_euphoria/
You can't say we're "C" bigots here - we've got every language you could think of. And here's one you'ld never think of - a version of Boggle written in Euphoria.
• boggle_jelson/
Here's one I wholeheartedly approve of. Not only does this one "get it right" (i.e. use the same algorithm as my own code ;-) ), it improves it by passing the trie walk along with the board walk, thus avoiding the unneccesary overhead of re-checking prefixes on each move, while pruning. Basically what I'd have written myself if I hadn't been in such a hurry to get something out. 10/10. Written by Jeremy Elson (jelson@circlemud.org)
• bsdboggle/
A replacement for the original Unix boggle which was proprietary to Sun. Uses an adjaceny matrix rather than a general DFS. The dictionary lookups are less than optimised. Display is cursor-addressed terminal, so should be portable to almost any environment. Originally from a Usenet post.
• duke_boggle/
Two for the price of one here. We have the C++ class's version (CPS108), and the Java class's version - the latter with both the staff version and one student's project. Note although there is a file in here called "Joggle" it is not the same as Robert Diamond's game which was withdrawn due to threats from Hasbro's lawyers.
• Guy McArthur's Joggle
A third program called 'Joggle'... this one is GPL'd. Here's the home page
• gtboggle/
My own effort. Short & simple; uses the DAWG data structure that almost all of my word games and utilities share. If you can't work out the recursive algorithm from this code, you're either not a C programmer or you shouldn't be. I recently made a quick hack to this to make it sort-of command line compatible with the old Unix boggle for use in Phil Goetz's genetic algorithm above. Also, chagrined at being out-programmed by Jeremy Elson ;-) I recently modified my code to do the more efficient parallel trie-walk that his does.
• macboggle/
Interestingly, this Boggle for the Mac is written in BASIC.
• niyi_boggle/
Client/Server networked Boggle in Java.
• mboggle/
Multi-user Boggle project in C. I have to say, creaking ancient programmer that I am, I find this stuff a lot more easy to follow than the multi-user Java versions above.
• boggle_ericm/
Smalltalk version.
• wordbox/
Boggle in Java for the Palm Pilot. And I didn't even know the Palm Pilot had Java.
• dboudah/
Boggle for OS/2 from David Boudah, with full IBM Classes code for the user interface. Main solving engine is in board.cpp. His explanation of the adjacency matrix is a bit more clear than that of the bsd version above.
• russhall/
Russ Hall's Boggle in BASIC.
• jared_tangleword/
Adrien Treuille's Tangleword (Boggle clone) solver. See the original web page to use it.
• deboggle/
• javaboggle/
• javascriptboggle/
• broggle/
• firekat/boggle/
• scorcher7/
• COMS40203/ (Bristol University exercise)
One of the student's solutions also includes a good user's guide. A sample solution is in boggle_mcternan/
One student's decompiled sources are here.
• bogged/ X windows game in wish (tcl/tk)
• ptkboggle/ Boggle in Perl/TK by godel@cmu.edu
• Perl Boggle
Another Perl boggle by Ronald J Kimball rjk@linguist.dartmouth.edu
• KX
I'm not sure, I think this may be an APL-related language which is embedded in some sort of X-windows display system.
• Boggle in Lisp by Jason S Cornez See the attached Usenet discussion...
• Johntology Boggle
• Mark Congdon's Wordcube Challenge and Solver
• Kent Smotherman's Java Boggle for the Palm Pilot

Finally, here are pointers to other boggle implementations for which we have not yet located source code:

Writing a boggle playing program is too easy, as you can see from the above. And it will always win. What we need is a way to make a boggle playing program interesting. Yes - it is possible to 'dumb down' a program by merely not claiming all the words it can find; it's even possible to do it fairly convincingly by restricting the program to a limited vocabulary more in line with that of your average human; but those are cheap shots. What would be a challenge is to make a boggle program behave like a real human, and do its best. Here's one approach I might be tempted to try: The boggle program does *not* have access to a word list. It can be trained on various word lists (like a human learning a language) but is has limited memory. It might explicitly store some frequently used common words, but the less common words can't be stored explicitly. Something like a hash table might be allowed, as long as it has less than perfect accuracy. A digraph and trigraph table might be OK, but not an exhaustive one. The program might even be allowed to look up some possible words once it has hypothesized them - but it might be limited to no more than X/2 lookups, where X is the average number of words that its opponent usually finds. This way the program is really trying its best under adverse conditions, in a way the human can relate to - and have a chance of beating. It's also important that the computer makes a few mistake - words it thinks may be plausible but which aren't in the dictionary. A neural-net version of Boggle would be fantastic! The human player will enjoy such a game much more than one in which the computer obviously knows all the answers but has decided just to throw the game to give the poor human a chance...