In this assignment, you will implement the game of Boggle, a word game in which players connect adjacent letters on a 4x4 board to create as many words as possible. This is based on an assignment at Stanford University in the corresponding Data Structures course, CS106B, modified for Java.

Program Specification

 The Game of Boggle

The Boggle board is a 4x4 grid onto which you shake and randomly distribute 16 dice. These 6-sided dice have letters rather than numbers on the faces, creating a grid of letters from which you can form words. In the original version, the players all start together and write down all the words they can find by tracing a path through adjoining letters. Two letters adjoin if they are next to each other horizontally, vertically, or diagonally. There are up to eight letters adjoining a die. A letter can only be used once in the 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.

In this assignment, the game play will differ slightly.The game contains a GUI to show the board, however, the game play will happen in the Console area only. There will only be two players: the human versus the computer. The computer player will find all the words on the board and store them in the program. The human player will get all the time they desire to find as many words as possible. Every time a human player guesses a valid word, they will be informed of their updated score. The scoring will simply count the number of guessed words (unlike in real Boggle where the length of words also counts towards a score). When they finish, they will enter an empty carriage return and then all the valid words as found by the computer player will be displayed to console.

The Dice

The letters in Boggle are not simply chosen at random. Instead, the letters on the faces of the cubes are arranged in such a way that common letters come up more often and it is easier to get a good mix of vowels and consonants. We provide you with code that handles the "rolling of the dice" that initializes the game board in the starter Boggle.java. The way to use it is as follows:

• Put cubes16.txt in the project folder (the directory containing the src/ and bin/ folders). It contains descriptions of the actual sixteen dice used in Boggle where each line of the file contains the 6 letters on the faces of each cube.
• The code contains just two methods. The rollDiceConfiguration() method uses the readDiceFile() method to read the cubes16.txt file to an ArrayList of Strings. The rollDiceConfiguration() method shuffles those die so that each die is not always in the same cell of the board and then selects a random side from each die to be the face-up letter. The output of rollDiceConfiguration() is a String such that the first four characters show up left to right on the top row of the board. The second group of four characters show up left to right on the second row of the board. And so on...
• In the method where you initialize the game (the Boggle constructor for instance), you could call rollDiceConfiguration() like this:

String letters = rollDiceConfiguration();

 The Game Play

Once your initialization is complete, you are ready to implement the computerTurn() and userTurn() methods. The computerTurn() method must use recursion to search for an exhaustive list of all the valid words on the Boggle board. The userTurn() simply needs to confirm whether or not a word is a valid guess and update the player score appropriately.

The computer's turn: computerTurn()

On the computer's turn, your job is to find all of the words on the board by recursively searching the board for words beginning at each square on the board. In this phase, the same conditions apply as on the user's turn, plus the additional restriction that the computer is not allowed to count any of the words already found.

As with any exponential search algorithm, it is important to limit the search as much as you can to ensure that the process can be completed in a reasonable time. One of the most important strategies is to recognize when you are going down a dead end so you can abandon it. For example, if you have built a path starting with the prefix "zx", you can use the lexicon's containsPrefix method to determine that there are no English words beginning with that prefix. So, you can stop right there and move on to more promising combinations. If you miss this optimization, you'll find yourself taking long coffee breaks while the computer is busy checking out non-existent words like "zxgub", "zxaep", etc. Not what you want.

The human player's turn: userTurn()

After the board is displayed, the player gets a chance to enter all the words he/she can find. Your program must read in the human player's guesses until he/she signals the end of her turn by entering an empty carriage return as her guess. Each time the human enters a word, you must check that the word fits the following constraints:

• The word is at least three letters long.
• It is defined in the lexicon as a legal word.
• It has not already been guessed by the user.
• It is one of the words found by the computer player.

If any of these conditions fail, you must print a message to console indicating which condition failed for that reason. Additionally, the word guessed by the player should not be added to their list of valid words. If, however, the word satisfies all these conditions, you should add it to the user's word list.

BoggleLayout.java

We have provided a simple Boggle GUI in BoggleLayout.java. In your program (Boggle.java), you can create an instance of a BoggleLayout:

BoggleLayout layoutObj;

You can use this layoutObj to display the 4x4 board of randomly configured dice by using the BoggleLayout constructor with two input arguments: (1) an integer indicating the number of dice on one side of the board, four in this case (2) a String containing the sixteen letters to be displayed. The first four letters in the string are on the top row from left to right. The second group of four letters are on the second row down from the top from left to right. And so on...

layoutObj = new BoggleLayout(4,"STNGEIAEDRLSSEPO");

 Solution strategies

In a project of this complexity, it is important that you get an early start and work consistently toward your goal. To be sure that you're making progress, it also helps to divide up the work into manageable pieces, each of which has identifiable milestones.

Here's a suggested plan of attack that breaks the problem down into the following four phases:

1.   Task 1-Read Assignment Specification. Take some time to look at what you've been given and how you might use it.

2.     Task 2-Find all the words on the board (computer's turn). Implement the killer computer player. Your computer player will make mincemeat of the paltry human player by traversing the board and finding every word the user missed. This recursion is an exhaustive search, so you will completely explore all positions on the board hunting for possible words. It is easy to get lost in the recursive decomposition and you should think carefully about how to proceed.

3.     Task 3-Human Player's turn Write the userTurn() loop that allows the user to enter his/her word guesses. Reject words that have already been entered or that don't meet the minimum word length or that aren't in the lexicon or the computer didn't find. Do not assume there is any upper limit on the number of words that may be found by the user. Once the human player is done, they will enter an empty guess to signal that they want the full list of all words found by the computer to be printed to console.

4.     Task 4-Test your code, add polish. Test each part of your code thoroughly such that it meets the marking requirements. Finish off the little details. Make sure you have error messages where appropriate. Comment each method. Clean up any code you write so that it is readable and natural to understand. Ensure that your code meets posted Style Guidelines as we will still be giving comments on your style. Write up a good Design Document file (the README) which is worth a significant portion of your marks for this assignment.

Using the Lexicon JAR We have given you a JAR file that contains the bytecode for the BSTInterface, BinarySearchTree, LexiconInterface, and Lexicon classes. You will use this jar file as a library in Eclipse instead of using the java class files from assignment 5. This is so that everyone is using the same implementation of the Lexicon assignment and so that no-one is penalized twice for assignment 5 if it was not completed. To use a jar file as a library in Java, the file must be included in the classpath explicitly. Here are instructions on how to include the JAR file in the classpath in Eclipse.

1.     Download the Lexicon.jar file and make a note of where you saved it.

2.     Create your Eclipse Boggle project if you have not already done so.

3.     Make sure that you have your Boggle project selected in the Package Explorer.

4.     In Eclipse select "File"-> "Properties."

5.     Select "Java Build Path" and then select the "Libraries" tab.

6.     Click on the "Add External JARs..." button.

7.     Browse to where you saved the Lexicon.jar file and select it by clicking "Open."

8.     Click "OK"

9.     Refresh your files by hitting F5 or right clicking and selecting "Refresh"

After you have added the Lexicon.jar to your project you should be able to access all of the public methods in the BSTInterface, BinarySearchTree, LexiconInterface, and Lexicon classes. For example, in your Boggle class you could have the following lines:

                this.lexicon = new Lexicon();

                this.lexicon.readFrom("dictionary.txt");

                this.lexicon.containsPrefix("PAR");

Deliverables and Marking

Please submit a zip-file containing the following:

1.     Any files that you have changed or created. At a minimum you should include the Boggle.java file. You have a lot of freedom in this assignment to create necessary classes. The only requirement is that you have one file called Boggle.java that contains a constructor and a playGame() method such that an external main() method can make the following calls to play Boggle:

Boggle boggle = new Boggle();

boggle.playGame();

• Do not include the Lexicon.jar file in your zip file.

3.     Because you are in control of how to design and implement this game, we absolutely will be reading a README for guidance. You MUST submt a .txt or .pdf file containing the following:

o    A description of how you designed your solution for Boggle including descriptions of any helper classes you had to make, the major data structures containing the dice, the game board and etc., and any other key design decisions you wish to elucidate.

o    Describe how to execute your program including any input arguments.

o    Describe what things you tried to test your code (i.e., Does your code for determining if the word is on the Boggle board work if a block has two adjacent letters that are the same?)

o    If any of the items are incomplete or not working exactly as specified, please make a note of them so as to help the graders assign partial credit.

Please submit your assignment on Moodle.

You will be graded on code correctness, style, and compilation. The following is the actual rubric to be used by markers during grading. Please ensure that you have met the following before submitting your assignment:

Program execution

 Your Boggle code can be called using the following lines in an external main() method.

Boggle boggle = new Boggle();

boggle.playGame();

Implement Computer player

• Recursive board search method has valid base cases.
• Recursive board search method has a valid recursive call that brings execution closer to the base case.
• Performs a successful fail-fast search for words
• Finds all the words that are on the board and in the Lexicon non-repeating.
• Prints all the words found by the Computer to the console window.

 Implement Human player

• Prints a title of the game to console.
• Human player can enter guesses until signifying they are done with an empty carriage return.
• On every guess, print out their updated score if they in fact made a valid guess.
• Check that the guessed words are at least 3 letters long.
• Check that it has not already been included in the user's word list.

• Check that guesses are defined in the Lexicon

o    If there is any valid check for the word in the Lexicon

o    Error message indicating that a guess does not constitute a valid word in the Lexicon.

• Determine that the guessed word was found by computer player.