Note: Projects are to be completed by each student individually (not by groups of students).
The objective of this project is to write a graphical version of the popular board game Boggle.
The code for the Boggle graphical user interface (GUI) is provided. Your task is to design and
implement the data structures and algorithms necessary for a computer player to play against a
human opponent. If you get everything right, the computer player should almost always win the
game by a large margin, but it will be fun to play anyway.
What is Boggle?
The game of Boggle is played with a set of sixteen letter cubes, which are standard six-sided
dice except that they are marked with letters of the alphabet instead of numbers. The cubes are rolled and arranged into a 4x4 square that might look like this:
The object of the game is to start at one cube and then work through a chain of letters to form a word that meets the following conditions:
For example, the sample pattern contains the word PEACE as follows:
- The word must be at least four letters long.
- The path traced out by the letters in the word must be connected horizontally, vertically,
or diagonally. You cant skip over intervening cubes to get the next letter.
- Each cube may be used only once in a given word.
The pattern, however, does not contain the word PLACE, which would require jumping from the P to
the L and then back to the A. Similarly, it is not possible to make the word POPE, because doing so
would require reusing the P.
Because the computer is guaranteed to find all of the words on the board (at least the ones in its
dictionary), we've tried to make the game a little more interesting by letting you find as many words
as you can first, and then turning the computer loose to find the rest. If you're thorough you can
tie the computer (although you will never beat it). Most games, however, end up as a rout, as
illustrated by the following diagram of the Boggle display at the end of a game:
The numbers on the top line represent the scores for the human and computer players, respectively.
Four-letter words score 1 point, five-letter words score 2, and so forth, with each additional
letter contributing one additional point. The human player in this example has found eight four-letter
words and one five-letter word for a total of 9 points.
The code for the GUI is provided. Your job is to implement the algorithm that searches the board for
words and the algorithm that determines if a particular word is on the board.
The following files are required to complete the project. You should download these files with a web
browser. You are not allowed to modify these files in any way except for implementing methods that
were intentionally left empty. Specifically, interface definitions may not be modified, and all code
must remain in the
boggle-delivery.zip : Contains all the below files.
In order for the game to work, you need to write a class that implements the
interface (defined in BogglePlayer.java). The Boggle graphical front-end will call your
class to execute the required back-end logic. Although you will probably implement other methods too,
your class that implements the
BogglePlayer interface must have at least the following methods:
These operations are described in the following sections.
public void loadDictionary(String fileName);
public boolean isValidWord(String wordToCheck)
public boolean isValidPrefix(String prefixToCheck)
public void setBoard(String letterArray)
public SortedSet getAllValidWords(int minimumWordLength)
public List isOnBoard(String wordToCheck)
public String getCustomBoard()
Three of the methods in the
BogglePlayer interface relate to loading and searching a word dictionary.
If Boggle is to run in a reasonable amount of time, all of these methods must be fast, even for
large dictionaries. For this reason, and to give you experience with binary search, you are required
store your dictionary as a sorted array of strings, and to use the binary search algorithm to search it.
You may assume that the provided dictionary file is already sorted, so creating such an array is easy.
loadDictionary method loads the dictionary from a file into an array of strings.
isValidWord method searches the dictionary for a particular word. It returns true
if the word is in the dictionary and false if it is not. This method should be implemented using
a binary search. If
loadDictionary has not yet been called, this method should
isValidPrefix method accepts a string and determines whether any words in the
dictionary begin with that string. It returns true if at least one word in the dictionary begins
with the string and false if not. This method should be implemented using a modified binary search
(i.e., think about how binary search can be modified a little to determine if any words start with
a given prefix). If
loadDictionary has not yet been called, this method should throw an
Hint: The dictionary is in lower-case and the Boggle board is in upper-case. Make sure you use the same case for everything so your binary searches will work. (Uppercase letters are considered "less than" lowercase letters.)
setBoard method accepts an array of
Strings of length N2 which specifies
the layout of dice on the N-by-N board. (In standard Boggle N is 4; but your
work for any square board.) The elements of the array specify the letters found on dice going from left to
right, and top to bottom of the board. (So the element indexed 0 is a string containing the letter(s) on the
die at the upper left corner; on a 4x4 board, the element indexed 3 is the top right letter, and index 15
gives you the letter at the bottom right.) Each string may be upper or lower case, and may contain one or
more letters. (In official Boggle, these strings will contain one character only, except for the double
letter die face "Qu"; but your
BogglePlayer should work correctly for arbitrary strings.)
From the array of strings to construct a data structure that represents the Boggle board in a way that
lends itself well to your search algorithms.
getCustomBoard method will be called by the GUI when the user requests a custom,
non-random board. This method should return an array of 16 strings representing the desired dice layout based on the usual index from 0 to 15.
Word Search Operations
The getAllValidWords method returns a SortedSet of strings containing all words on the board that:
- are of at least the given minimum length
- are in the dictionary
- can be found by following a simple path on the board (remember, each square can
participate at most once in a given word)
setBoard has not yet been called, this
method should throw an
One technique for finding all words on the board is to recursively follow all paths through
the board, keeping track of all valid words that are found along the way. Of course, there are many
paths to be followed. If Boggle is to run in a reasonable amount of time, your algorithm will need
to be intelligent about avoiding wasted effort. One way to speed up the search is to only follow
paths that have the possibility of leading to valid words. Before moving along a path, the search
algorithm should ask the dictionary if any valid words begin with the prefix represented by the
current path. If the answer is no, there is no need to follow the path further. Checking prefixes
in this manner will allow your algorithm to avoid a lot of dead-end paths, and therefore run much
more quickly. In fact, if you dont do this, your program will run too slowly to pass off.
isOnBoard method accepts a string argument and determines whether the string
can be found on the board. The return type of this method is a
List object containing
Integer elements. If it is possible to find the word on the current board, the method
returns a list of
Integers representing the locations of the dice used to form the word,
in order (using the same mapping from integers to locations required by
If it is NOT possible to form the word, the method returns
null. Again, every effort
should be made to avoid following dead-end paths. If
setBoard has not yet been called,
this method should throw an
Since the GUI front-end does not know the name of your
BogglePlayer implementation class,
you will need to modify the
BoggleFactory class to create an object of your class and
return it. The GUI will then call the
BoggleFactory to create the
BoggleFactory class is found in BoggleFactory.java.
The Boggle GUI is implemented in BoggleGUI.java. Boggle may be executed with the
java cp project-dir cs235.boggle.BoggleGUI word-file board-size min-word-length
For example, if your project files are stored in a directory named
- project-dir is the directory that stores the code for the project (required).
- word-file is the name of the dictionary file (optional, defaults to dictionary.txt).
- board-size specifies the size of the board (optional, defaults to 4).
- min-word-length specifies the minimum word length (optional, defaults to 4).
\projects\boggle, the dictionary file is named
dictionary.txt, and you want a 5x5 board with a minimum word size of 3, the command to run Boggle would look like this:
java cp \projects\boggle cs235.boggle.BoggleGUI dictionary.txt 5 3
The file TestDriver.java contains a test driver program that you may use to test your implementations of
BogglePlayer. The test driver is designed to test all of the functionality described in the previous sections. However, the test driver should not be viewed as a replacement for doing your own testing. If your code passes the test driver, it is still possible that it will fail at pass off because a different test program is used for pass off (i.e., the pass off driver). It is your responsibility to make sure that your code works.
Write a class that implements the
BogglePlayer interface. Your implementation class
must be in the
Store the dictionary as a sorted array of strings. Use binary search to search the array for words and prefixes.
Avoid following dead-end paths, thus allowing Boggle to run quickly on larger boards.
BoggleFactory class to return one of your
After fully testing your code, go through the submission process and then meet with a TA for a pass off interview.