1 Introduction

You'll be programming a Boggle game with an unbeatable computer player. Read all this before beginning. Before we move on to the actual programming, let's review the rules of Boggle.

Boggle consists of 25 dice, each of which have different letters on the six faces (one face of one die has a "Qu"). The dice are rolled, and placed at random in a 5x5 grid, so that they look like this:

Players then have 1 minute to find as many words in the letters as they can, moving horizontally, vertically, or diagonally one space. For example, the above board has the word "TIN," starting in the upper right, moving to the left one spot, then moving diagonally, down and to the right. Dice may not be reused in a given word. For example, the above does not have the word "TINT," because we may not reuse the "T" in the upper right in a given word.

Scoring depends upon the number of letters in the word. Words with 3-4 letters get 1 point, words with 5 letters get 2, 6 letters gets 3, 7 letters gets 5, and 8+ letters gets 11.

There are two different programming challenges in this assignment. The first, is we will need a data structure to store words in. The second, is we will have to find out which words exist in a given Boggle board.

2 Programming Your Data Structure

You will need a data structure to hold Strings, which you program yourself (no using Java's), and which implements the following methods (you will want to be exact about the method signature, as I'll give you code that uses some of these):

• void insert(String word): This method inserts this String into the data structure. If the word already is in the data structure, it should not add it again.
• boolean find(String word): This method tells you whether the String word appears in this data structure.
• Queue<String> traverse(): This method returns a Queue filled with all Strings that appear in the data structure. Because you are already an expert on Queues, you may use Java's built-in Queue interface, which is implemented by LinkedList and ArrayDeque.
  (e.g. Queue<String> q = new LinkedList<String>();).

It is your choice what data structure to use, but as you will see, there are rewards for it being fast.

Your program will have two instances of your data structure: one to hold every word in the English language, and one to hold the words that your program finds in the Boggle board.

3 What I'm Giving You: A Tour

• american-english
• Board.java
• OnePlayer.java
• TwoPlayers.java

You can get all these files at once by downloading the file proj2.tar.gz and running tar xzvf proj2.tar.gz

american-english is a text file consisting of every word in the English dictionary which uses the standard 26 letters (no accented letters). There are 64,117 words in this document.

Board.java is where a lot of the magic happens. Places that need your attention are labeled with TODO.

• A Board instance has three class variables; a 2-dimensional char array (for encoding the dice rolls), an instance of your data structure called englishWords (for holding every word in the English dictionary), and a random number generator (for rolling the dice before you start).
• There are two constructors, one of which takes a seed for the random number generator, and one which does not. The one that accepts a seed makes debugging easier, as you'll get the same Boggle board every time as long as you use the same seed. Both constructors call two functions to set up the game:
• initDictionary() reads every word from the file american-english and adds it to englishWords. You have one line to repair so it builds your data structure.
• initBoard() handles the rolling and placement of the dice, based on the actual dice that come with a game of Boggle. When it is done running, the field board is filled with chars. You don't have to do anything for this.
• toString() is a toString. It's used when printing the Board, and uses fancy unicode characters to draw a box around it. You don't have to do anything for this.
• static countPoints(Queue<String> q) takes a Queue full of Strings, and returns the number of points that word list gets in Boggle. You don't have to do anything for this.
• Queue<String> allWords() returns a Queue full of all words that appear in this game of Boggle. It requires a lot of work. First, it creates a 2-D boolean array called used. Remember how a given word may only use each die once? This array encodes which die have been used. It starts as all false. Second, you'll build an instance of your data structure called foundWords to hold all the words that you find. Then, for each possible row and column combination, you'll call the recursive helper method.
• void allWords(String sofar, int row, int col, boolean[][] used, YourDataStructure foundWords) is the recursive helper method to do the heavy lifting. The String is the word as built so far. row and col are the row and column we're currently on. used encodes which dice have been used already, and foundWords is there to get filled when we encounter actual English words. Obviously you'll want to change the type of foundWords to be your data structure. In order to speed things up, go ahead and assume no words exist longer than 8 letters. If your final product is fast enough, perhaps you'll be able to take that restriction off (my solution doesn't have it).

TwoPlayers.java is already written to allow you to play against the computer; you just have to set the type of your data at one or two spots. This is fun when you've finished, to see how badly you're beaten by the computer (very badly).

OnePlayer.java is a main method used to see what words the program found in the board. This also does the timing that we'll use for the contest.

4 What You'll Give Me

You'll submit all .java files, along with a README.txt telling me about what you did. What data structure did you use? Which of the below steps have you reached? What citations do you need to include?

5 Grading

Step 1 (up to 70 points): Finish the project with a Binary Search Tree as your data structure.

Step 2 (up to 100 points): Make some improvement on the above to make it faster. AVL Tree? 2-3-4 Tree? A cleverly-sized Hashtable? Something else you learned about on the internet? Defend your choice in your README.txt. What's the runtime of your three methods?

You can change anything you like about the program to speed it up, as long as OnePlayer still works and everything you submit is your very own code.

There are rewards for fast code!

5 extra-credit pts: You successfully finished Step 2, and OnePlayer.java runs faster than anybody else's in your section.

1 pt extra credit FOR YOUR ENTIRE SECTION: You successfully finished Step 2, and OnePlayer.java runs faster than anybody else's across all three sections.

6 Other Notes

Please thoroughly comment your data structure, so it is easy for me to understand. Additionally, please comment the method allWords() in Board.java.

In attacking this project, I recommend starting with a BST, even if you have grander designs. So, make the BST, and make sure the methods it needs have work. Then work on the Boggle algorithm. Once that works with a BST, then you can swap in different data structures.

Don't forget that Q is automatically followed by a 'U.'

The project must be written in Java.

If you find yourself getting a StackOverflowError, there are two possible reasons for this. One, you have infinite recursion taking place. Two, your data structure isn't great, and it's just gotten too tall. You can increase the size of the stack allowed by Java by using the -Xss flag. The following runs OnePlayer with 2MB of stack space:

java -Xss2m OnePlayer

7 Example Output

This file contains the result of running my program with java OnePlayer 0

This file contains the result of running my program with java OnePlayer 10

This project was created by Gavin Taylor at USNA and inspired by one written by Owen Astrachan at Duke University.