Compsci 100, Fall 2006, Boggle®

Check out the code by snarfing boggle from" or by browsing the code directory. All the javadoc for the classes is accessible too.

Check out the FAQ


Boggle® is a word game that some find fun to play and for which it is possible to write a brilliant computer-player, e.g., one that finds all words blindingly fast.

A boggle board is a 4x4 grid (or 5x5 for Big/Super Boggle) of boggle cubes which are similar to dice. These 6-sided dice have letters rather than numbers on the faces, creating a grid of letters on which you form words. In the original version, the players all start together and write down all the words they can find by tracing by a path through adjacent letters. Two letters are adjacent if they are next to each other horizontally, vertically, or diagonally. There are up to eight letters adjoining a cube. A letter can only be used once in forming a word, but can be used in more than one word. When time is called, duplicates are removed from the players' lists and the players receive points for their remaining words based on the word lengths.

For example, the screen shot below shows the result of one game in which the computer has significantly outscored the human. One word, reinstate found by the computer is shown highlighted on the board when the user clicks on the word in the GUI.


Your assignment is understand the classes and interfaces in a GUI-based version of Boggle. You're supplied slow, simple implementations of some classes and you'll have to write more efficient implementations. You'll also need to implement two classes using two different ideas that allow the computer to find all words on a board.

You'll implement more efficient versions of a lexicon or dictionary that facilitate looking up words and prefixes for words more efficiently than the class you're supplied.

You'll also implement two methods for automatically finding all words on a Boggle board. Each method requires writing a recursive routine based on flood-fill, the method we study/studied in class as part of the blob-finding program.

Implementing Lexicons

You'll write three new classes for this part of the assignment. Two are lexicon implementations and one is a class for testing your implementations. You may want to write the testing class first based on the provided SimpleLexicon so you can then test your new implementations.

In Boggle, legal words are those found in the lexicon associated with a game's model. A lexicon is simply a list of words, it's not a dictionary because it doesn't have associated definitions for each word.

The ILexicon interface specifies the methods exported and useful for a lexicon. You're given an implementation SimpleLexicon implementation that has an O(n) implementation of the method wordStatus since the implementation simply does a linear search over the list of words it stores. Read the documentation for details of the interface, an inheritance diagram is given below.


You must write two new, efficient implementations. The first is based on using binary search on an ArrayList so the class will have an O(log n) implementation of wordStatus. The second is based on a using a trie, so it has an O(word-length) implementation, regardless of how many words are in the lexicon. This is essentially an O(1) implementation since the complexity doesn't depend on the size of the lexicon.


You must write a class named BinarySearchLexicon implementing the ILexicon interface. Base your implementation on SimpleLexicon but don't worry about duplicating code in your implementation. Store words in the lexicon in a sorted ArrayList and use Collections.binarySearch to search the list. You'll want to read the documentation for binarySearch. In particular, note that when the value returned is less than zero the value can be used to determine where a word should be in a sorted list. For example, when looking up "ela" the value returned might be -137. This means that "ela" is not in the lexicon, but if it were to be inserted it would be at index 136. This also means that if the word at index 136 does not begin with "ela" then no word in the lexicon has a prefix of "ela". So, any non-negative value returned by binarySearch means the status of a word is WORD. If the value returned is negative, one call of the appropriate startsWith string method can determine if PREFIX should be returned (make sure you don't go off the end of the array of words in the lexicon when calling startsWith).


For A-credit you must implement a lexicon based on a trie data structure. You should be able to use the code we've seen in class as the basis for your implementation. To facilitate iterating over the words in the lexicon you should store the words in a trie and in a set. The trie will support basically constant-time implementation of wordStatus and the set will be used only for supplying an iterator when the lexicon's words are accessed in order via its iterator.


To test your lexicon implementations you should create a class LexiconTester. The main method of the class should create a lexicon, initialize it, and test its wordStatus method with different strings and check the anticipated return value. For example, you could construct a Scanner from a String such as "big bigger small smaller sun" by creating a scanner from the string, loading the lexicon, and then calling wordStatus and checking the value returned. Your test class should print errors using System.out. If all tests pass, the class should print nothing. Here's an idea for what your code might look like.
public static void test(ILexicon lex) {

   String[] words = { "cpt", "cat", "cas" };

   LexStatus[] stat = { LexStatus.NOT_WORD, LexStatus.WORD, LexStatus.PREFIX };

   for (int k=0; k < words.length; k++){
       LexStatus ls = lex.wordStatus(words[k]);
       if (ls != stat[k]){
          System.out.println(words[k] + " got "+ls+" expected "+stat[k]);

Finding Words

You'll implement two classes for a computer finding all words on a Boggle board. Each class requires writing a recursive method similar to the flood-fill code we've studied.

One class will iterate over the lexicon looking up every word in the lexicon on the board. The other will try every possible string on the board, looking up the strings in the lexicon. The first class potentially searches for lots of words that aren't on the board, so the implementation should "fail fast", i.e., minimize the search when a word isn't on the board. The second should avoid searching for strings that can't be part of a word. This is why the lexicon method wordStatus returns a value you can use to avoid searching uselessly.


You'll write/implement a class WordFinder implementing the IWordOnBoardFinder interface. This method takes a Boggle board and a string and returns a list of BoardCell values for the string as found on the Boggle board.

When you've implemented the class, you should call setFinder of BoggleModel with a new WordFinder object. If your class works, you can play a game and click on a word the user enters. The words cubes should be highlighted as shown in the screen shot at the beginning of the handout.

Implementation Ideas

The idea is to look for the string by starting at every possible Boggle cube, i.e., at every row,column of the Boggle board. If you find the first character of the string you'll continue searching in adjacent cubes for the second character. If that's found you'll look at adjacent cubes for the third character and so on. You shouldn't use a cube more than once for a string and you stop searching for a string on the board when no cube matching the current character in the string is found or when the entire string is found.

For example, when looking for "TUNE" in the board at the top of the page, there are two cubes from which a search could start since there are two cubes whose face shows "T". However, no cube adjacent to the "T" cubes has a "U", so the search for "TUNE" will fail when looking for the second character.

The cellsForWord method will call a private, helper method that does the work. This was the same idea used in the blob-finding code we studied. The helper method will have as parameters at least the following:

You may have more parameters, or use instance variables rather than parameters. Parameters are likely better than what are essentially global variables. For example, you could pass as a parameter an ArrayList that will have BoardCell values added to it as cubes are found that correspond to the the current character in the string being searched for.

The helper method will make eight recursive calls to check all adjacent cubes. Cubes that have been used in forming a string should not be re-used.

You might find it useful to have the helper method return a boolean value indicating whether the string searched for is found. If the face of the cube at the specified row, column in the helper method doesn't match the current character of the string then false is returned. If the face does match, and the cube hasn't been used in forming the current word, then a BoardCell value corresponding to the cube is marked as used/added to a list of BoardCell values. Then eight recursive calls are made looking at adjacent cubes for the next character of the string.

When the index of the current character being searched for is greater than the length of the string then all characters have been found and the method returns true. If no recursive call returns true then the BoardCell last marked/added to the list is unmarked/removed from the list so that it might be used later in forming the current word.

Be careful when finding a "Q" in a word since if there's a match the Boggle board cube has two characters and you'll have to take action to search appropriately.

IAutoPlayer Implementations

You'll write two classes that let the computer find all valid words on a Boggle board. Each class will extend AbstractAutoPlayer and thus implement the IAutoPlayer interface. When you implement method getAllValidWords you should first set the autoplayer's score to zero and the clear any words already stored. This requires accessing the appropriate inherited state from AbstractPlayer directly, e.g., you'll write
   myScore = 0;
where instance variable myScore is in AbstractPlayer.

Here's a diagram of some of the classes and interfaces in the player hierarchy, the IPlayer interface at the root of the hierarchy isn't shown.



Once you can find the cubes that form a word you can write/implement class named LexiconFirstAutoPlayer that extends AbstractAutoPlayer. To find all the words on a board simply iterate over every value in the lexicon checking to see if the word is on the board by calling the model's cellsForWord method that now works based on the class WordFinder you write in the previous section.

You can then add this auto-player to the BoggleGui by changing the code in BoggleMain.

You should then be able to play a complete game and have the computer find all the words on the board. This requires only a modification of the main method to create the auto-player based on the WordFinder method.


Rather than iterating over every every word in the dictionary you can use the board to generate potential words. For example, in the board shown in the screen shot below the following words can be formed starting the "L" in the upper-left corner: lore, lose, lost, lot. From the output it's clear that "loser" isn't in the lexicon since it is on the board, but isn't shown in the output.


Starting at the cell "R" at [1,3] (recall the first row has index zero) we can form "REST" and "RESORT". Starting at the cell "R" at [0,2] we can form "ROLL" and "ROSE" as well as "REST".

Since no word begins with "GT", "GP", "GS", no search will proceed from the "G" in the lower-right after looking at more than two cubes since these two-character prefixes aren't found in the lexicon.

You'll write a recursive helper method for this class to find all the words starting at a specified [row,column]. The basic idea is to pass to this helper method at least the following:

When first called, the string built from the search so far is the empty string: "". The current cube/cell on the board, if legal and not used in the search so far, is added to the end of the string built so far. If the string is a word, the word is added to a set of strings that will eventually be returned from the original call to getAllValidWords (this set might be a parameter to the helper method you write). If the string is either a word or the prefix of a word in the lexicon then the search is continued by calling the helper method for each adjacent cube with the string built so far. If the string is not a prefix (or a word) then the search is cut-off at this point and will continueom the method that called the failed-method, which is either the original getAllValidWords or some recursive call that call generated.

As with all flood-fill/backtracking code you must make sure your code doesn't re-use a cube once it has been used in the current search. This means that each cube that contributed to the string built from the search so far can't be re-used in extending the string. But the cell/cube can be re-used when searching for different strings/starting from or continuing from different cubes.


Boggle boards are generated by the BoggleModel class when its makeBoard method is called. This method generates a board by calling BoggleBoardFactory methods. This factory uses a random number generator with a specific seed so that when you start a sequene of Boggle games the same boards are generated (e.g., if you use only 4x4 boards the same sequence of boards will appear each time you launch the program.)

You can ensure that new,random boards are generated by calling the setRandom method of the BoggleBoardFactory class with a java.util.Random object created without a specific seed, e.g.,

  BoggleBoardFactory.setRandom(new Random());

When debugging you may not want to do this to ensure that you have repeatable behavior. In your final program you'll probably want users to have a different sequence of boards every time.


Write a class named BoardStats that generates 1000 boards starting with a java.util.Random object initialized with a seed of 12345.
  BoggleBoardFactory.setRandom(new Random(12345));

The class should find all the words on the board using BoardFirstAutoPlayer and print the highest-scoring board found out of the 1000 boards. The class should repeat this "experiment", again starting from a newly created random number generator seeded with 12345, generating 1000 boards, and printing the highest-scoring board but this time using LexiconFirstAutoPlayer to find words on each board.

Your code should print the total time taken to process the 1000 boards with each of the two auto-player classes. In your README be sure to document your findings including the highest scoring board and the time taken by your methods.


This assignment is worth 40 points, the breakdown is as follows:

functionality points
WordFinder 9
BinarySearch lexicon 4
Trie lexicon 5 (extra)
Lexicon tester 4
Lexicon-first auto 9
Board-first auto 4
Stats 1000 games 6

Your README file should list your testing results, all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimate of how long you spent on the program and what your thoughts are about the assignment.

Submit your README and all of your source code using Eclipse with assignment name boggle.

Owen L. Astrachan
Last modified: Fri Oct 13 11:30:27 EDT 2006