CompSci 100 Boggle® Assignment

Thanks to Julie Zelenski, Paul Kube, and Owen Astrachan for this assignment.

Menu

Background

Boggle® and other variants are word games where you try to find all the words on a board. 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 on which you form words. In the original version, the players all start together and write down all the words they can find by tracing by 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 cube. 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.

Your assignment is to write a program that plays a fun, graphical rendition of this little charmer, adapted to allow the human and machine to play pitted against one another. As you can see from the screen shot above, the computer basically trounces all over you, but it's fun to play anyway.

The main focus of this assignment is designing and implementing the data structures and operations on them that will efficiently find words that appear in a Boggle board. Because your focus will be on the back-end logic, you will be provided with a graphical display program, BoggleGUI. This program knows how to generate and render a random Boggle board, interact with a human player, and display results of the game. It will use your code to verify input from the human player, and to obtain the computer player's results. There is still a lot of work left for you, so definitely do not postpone this assignment until the night before.

Setup

Please checkout the code under assignments/boggle using Ambient Eclipse or otherwise download the code from the code directory.

What you will complete

Your task for this assignment is to implement the following functionality
  1. Write code to determine whether a particular word is on the board
  2. Improve the efficiency of the lexicon (word list) using a Trie
  3. Create computer players that return a list of all words on the board by using two methods
    1. Checking if each word in the lexicon is the board: lexicon-first search
    2. Checking if the letters on the board form words in the lexicon: board-first search
  4. Report how the various methods compared in terms of complexity

Classes

The following key will help you navigate through the various files

Board Representation

Model/View

As in previous assignments, the model and view together comprise the main portion of the program.

Lexicons

You will need to verify words by looking them up in a lexicon. Although the word lexicon is often used as a synonym for dictionary, lexicon does not imply that the words have definitions in the way that dictionary entries do. All you need to know is whether a word is in the list. The lexicon abstraction provides this capability.

Players

Useful classes

Dictionary Files

How the Boggle program works

In the computer version of the game, the human player gets to go first. The player proceeds to enter in the text area at the bottom of the window, one at a time, each word that she finds in the game board. A valid word must meet four requirements: (1) it must contain at least the minimum number of letters, (2) the word must not already have been entered by the player, (3) the word can be formed from the letters showing on the board following in order a path through neighboring dice without using the same die twice, and (4) the word must exist in the official lexicon of words. All valid words entered by the player are highlighted graphically on the board display. The computer player determines the validity of the words, but we assume it can be trusted to do so fairly.

Unlike the original version, there is no time limit here. Instead, the player indicates that she is through entering words by hitting a lone extra carriage return, as if entering an empty word. At this point, the computer gets to take its turn. The computer searches through the board looking for all the valid words it can find. The computer typically beats the human player mercilessly, but the player is free to try again by starting a new game. Scoring is as for the original version of the game, except that words are not removed from the players' lists (if they were, the human player would never have any words left!).

You can run the BoggleGUI application as given. You will be able to start new games, but the board search is not functional, so every word will give the error message to the right.

Implementing isOnBoard

Your first step is to complete the isOnBoard method of the BoggleModel class. This method takes as argument a String and determines whether the String can be found in the board. The return type of this function is a List object containing BoardCell elements. If it is possible to find the word in the current board, the function returns a list of BoardCells representing the locations of the dice used to form the word, in order. If is is NOT possible to form the word, the function returns null. In order to determine whether a word appears on the board. You will need to start from a location and examine neighboring positions recursively to determine if the string exists. To increase efficiency, you can also try building a map from letter to positions, so it is easy to find where a particular letter is or is not. Note:

Lexicon

You are given the SimpleLexicon implementation of the Lexicon abstraction. Write TrieLexicon that will use a Trie to represent the lexicon and enable fast wordStatus calls.

Searching for all words

You will implement 2 computer player that implement the IAutoPlayer interface. The difference between the searches is whether the lexicon drives the search or whether the board drives the search. The crucial method is getAllValidWords which returns, as a SortedSet of Strings, all the words that
  1. are of at least the given minimum length
  2. are in the Lexicon given by the BoggleModel
  3. can be found by following a simple path on the board as determined by BoggleModel

Lexicon-first

The computer player's task is to find the intersection between paths on the board and words in the lexicon. One can find this intersection by iterating over the words in the dictionary, looking up each on the board. You should now have a working BoggleModel.isOnBoard, so implementing the computer player should be straightforward. You should create a new class LexiconFirstAutoPlayer that may extend DummyPlayer and implements lexicon-first in the getAllValidWords method.

Board-first

In order to find all words, your program needs to exhaustively recurse over all paths through the board, checking with the dictionary to identify those that are words. There about 12 million distinct paths through a 4x4 Boggle board, so it can be time-consuming to check them all. By using the ILexicon.PREFIX value, you can avoid wasting time examining paths down dead-end prefixes such as "qxz". With prefix-pruning, the board-driven search only examines should finish in a blink of an eye.

For extra credit, note how many paths your search examines on average.

Testing and Submitting

Testing

You should add code BoggleStatsGenerator to time your different board-first and lexicon-first searches. Your README should include timings and observations about the tradeoffs between the two approaches. You should discuss how the two methods would fare as the board size or lexicon size increases. Besides timing tradeoffs, you should discuss the complexity of the two approaches in terms of programming time and maintainability.

Submitting

This assignment is worth 35 points, the breakdown is as follows:

functionality points
isOnBoard 8
Better lexicon 6
Lexicon-first search 6
Board-first-search 9
README/testing 6

Your README file should list your testing results, all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimated of how long you spent on the program and what your thoughts are about the assignment.

Submit your README and all of your source code using Eclipse with assignment name boggle.

Jeffrey R.N. Forbes
Last modified: Thu Apr 7 01:47:28 EDT 2005