Lab 8 - A Boggling Design

Due: Monday, April 23, 2007 by 10:00am (start of class)

For this lab, you'll be working in groups of two. Choose a partner to work with on the assignment. Each member of each pair should begin by reading the description of the problem. Discuss it with your partner until you both understand the problem. Then work together to design a program which will be able to solve it.

Your job is to produce a set of design documents that can be used as a blueprint for the actual implementation of a Boggle program. The implementation will be assigned as your final lab assignment.

The game:

The game uses 16 dice. Each one has a letter on each of its six faces. (A list of the 16 6-letter dice arrangements is found in the file dice.txt.)

To start play, the 16 dice are shaken and placed at random in a 4x4 tray, resulting in a single 4x4 grid of letters, as shown below. (Only one of the faces of each die is visible.) There are two forms of randomization at work here. The placement of the dice in the 4x4 grid is random, as is the choice of which face of each die is visible.

When the letter tray is formed, a three minute timer is started. Each player has three minutes to write down as many words as possible which can be found in the letter tray. Each word must be found on a path from letter to adjacent letter, going horizontally, vertically, or diagonally, without using the same letter cube more than once. For example, the word "MURALS" can be found in the grid as shown below.

At the end of the three minutes, the players' word lists are compared. Any word that appears on more than one list is crossed off of everyone's list. Then each player's score is calculated by assigning points to each remaining word on his word list, according to the following table:

number of letters:	3	4	5	6	7	8 or more
points:	1	1	2	3	5	11

For the complete game rules see http://www.centralconnector.com/GAMES/boggle.html.

I'm providing two files which your program can use. You can download them from the links below.

• lexicon.txt -- a file containing over 40,000 words, all lowercase letters, one word per line
• dice.txt -- a file containing the letters that appear on the 16 Boggle dice, six letters per line
  Note: append a 'u' to the letter 'Q' to make it more useful just as in the real version of Boggle

The Program Requirements:

Your assignment is to design a program which implements a modified form of Boggle that allows a human player to play against the computer, or one human to play against another. The modified Boggle will be played as follows:

• When a human plays the computer, let the human player find as many words as possible, then let the computer find any words that the player may have missed.
• When a human plays another human, let them each take a turn, finding as many words as possible.
• Words must be at least 4 letters long.

• Read the letter dice from a file, "shake" the dice, and display the tray of dice. (Note: For testing purposes, it will be useful to have an option in which the dice are not shaken.)
• Allow the player to enter words, one at a time, that he or she can find on the tray.
• Calculate the player's score by scoring all words that are at least four letters long, can be formed by the letters on the tray, and are in the lexicon.
• Find and display all the words on the tray (computer's turn) that the user did not find.
• Display the scores of the human players and the computer.
• Allow the user to play again.
• Display the rules of the game.
• Have a GUI.

Optional features (or think of some others on your own):

• Use a "timer" to allow a player to have only a limited amount of time to enter words.
• Allow the user to enter words by clicking on the dice.
• Allow for more than two human players.
  
• Graphically display the words found on the tray using blinking letters or by changing the color of the dice.

Suggestions:

1. Code Reuse -- You may find it useful to use some of the classes from the Java API in your design. Your UML class diagram should indicate where you are using Java classes.
2. Letter Dice -- "Shake" the tray of letter dice by randomly picking a face to display for each die, then loop over all the dice and swap each one with another that is chosen at random.
3. Lexicon -- It will be important to look up words quickly. We'll be studying in class some data structures and algorithms that will make it possible to search the lexicon quickly. One way to improve the search is to stop searching for a string if the lexicon does not contain a prefix of that string. For example, there is no point continuing to form strings from the prefix zx, since there are no words in the lexicon that start with those letters.
4. Player's turn -- When the user enters words, reject any words that have already been used, don't meet the minimum length requirement of 4 letters (real Boggle uses 3), can't be formed in the current letter tray, or aren't in the lexicon.
5. Word search -- There are two types of word searches required for this program:
   • Searching for a specific word -- Think about how you could use recursion to search for a specific string on the letter tray. Remember that the letters used to form words must be adjacent and cannot be used more than one time in a single word. As soon as your recursive routine realizes that a player's word can't be formed from a given starting position on the board, move on to the next position.
   • Searching for all possible words (computer's turn) -- This time you perform an exhaustive search for all possible words formed by the letters on the board. This problem can also be solved using recursion, but it is more complicated.

The Design Process

Once you are settled on the CRC cards, you can create a UML class diagram showing the classes and the relationships between them. The UML diagram for each class lists its attributes and methods, so you are getting closer to the specifics of a Java implementation now. Indicate what data structures are used by each class. Each method is specified by its signature; that is, its parameter list and return value. In addition, you should provide a brief description in English of what the method is supposed to do.

Next, you should start thinking about the play of the game as a sequential process. Create UML sequence diagrams which outline the steps that your program will take in response to actions of the actors (that is, the human players).

The word search algorithms form the real engine of the game. Outline a specification for the search algorithms that the game will need to implement.

Your design should be well thought out, clear and well documented. Where appropriate you should incorporate the fundamental object oriented principles of code reuse, data abstraction, information hiding and inheritance.

I've installed a tool called Violet on the CS machines that you can use to draw the various forms of UML diagrams. You should be able to run it simply by typing violet on the command line.

What to Hand In:

• CRC cards
• UML class diagram
• UML sequence diagrams
• A text file in which you briefly describe each class and method in your class diagram

Looking Forward...