Boggle

Note: Projects are to be completed by each student individually (not by groups of students).

Introduction

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:

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.

For example, the sample pattern contains the word PEACE as follows:

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.

Project Files

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 cs235.boggle package.

boggle-delivery.zip : Contains all the below files.

BoggleGUI.java
BogglePlayer.java
BoggleFactory.java
TestDriver.java
dictionary.txt

BogglePlayer

In order for the game to work, you need to write a class that implements the BogglePlayer 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:

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()

These operations are described in the following sections.

Dictionary Operations

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.

The loadDictionary method loads the dictionary from a file into an array of strings.

The 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 throw an IllegalStateException.

The 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 IllegalStateException.

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.)

Board Operations

The 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 BogglePlayer should 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.

The 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)

If either loadDictionary or setBoard has not yet been called, this method should throw an IllegalStateException.

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.

The 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 setBoard). 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 IllegalStateException.

BoggleFactory

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 BogglePlayer object. The BoggleFactory class is found in BoggleFactory.java.

Running Boggle

The Boggle GUI is implemented in BoggleGUI.java. Boggle may be executed with the following command:

java cp project-dir cs235.boggle.BoggleGUI word-file board-size min-word-length

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).

For example, if your project files are stored in a directory named \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

Testing

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.

Requirement #1

Write a class that implements the BogglePlayer interface. Your implementation class must be in the cs235.boggle package.

Requirement #2

Store the dictionary as a sorted array of strings. Use binary search to search the array for words and prefixes.

Requirement #3

Avoid following dead-end paths, thus allowing Boggle to run quickly on larger boards.

Requirement #4

Modify the BoggleFactory class to return one of your BogglePlayer objects.

Requirement #5

After fully testing your code, go through the submission process and then meet with a TA for a pass off interview.