Homework Assignment 3

The Game of Boggle

15-211 Summer 2010

July 26th, 2010 at 11:59:59pm


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 goal of the game is to start at one letter and then walk through a chain of letters to form a new word that meets the following conditions: For example, the above grid contains the words CENT and BLEEP as follows:
Read the Wikipedia page on Boggle.


Theory Questions: 15 points

In the file theory.pdf there are some short theory questions. Please answer the questions in this file and turn it in class.

Starter Code

Download the starter code for assignment (zip file). Once you finish implementation, FTP java files to /afs/andrew.cmu.edu/course/15/211-kesden/handin

What to Submit

You FTP the following java files

Do not submit anything else like zip files, folders, desktops, class files. Make sure you do not use packages in your java files as well. Failure to do so will result in a 20 point penalty.

Playing Game

This assignment involves an interactive graphical application. Run GameApplet.java as a Java applet to play the game.

Trie: 40 points

A Boggle engine needs to know not only whether or not a word is in the dictionary, but whether or not a word (or, more precisely, a sequence of letters) is a prefix of a word in the dictionary. The best underlying structure that supports such dictionary is a trie - an N-ary Tree, where edges are labeled with characters and thus each path from the tree root to some node represents a prefix (or an entire word).

See the provided interface TrieInterface.java for implementation requirements.

BFS Algorithm: 35 points

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 here is to detect as soon as possible that no words are possible down a particular path. For example, no words in English begin with the letters ZX. Thus, if you are searching through the board and have built a path starting with this letter combination, you can stop right there because no additional letters will end up making a word. Note that the trie allows you to determine whether a given set of letters ever appears at the beginning of a word.

Setting up the board

The letters in Boggle are chosen at random from the following set of 16 cubes. The characters in the group indicate what letter will appear on the six faces of each cube. For each game, the GUI will shuffle the letter cubes into a new configuration and pick a random side of each cube to display on the screen. The resulting board is stored as an array of strings for use by your backtracking algorithm.


Coding Style: 10 points

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate data structures and algorithms were used, as well as judge the overall style of your code. Programs will be graded both on correctness as well as their ability to deal with so-called edge cases, like empty lists, lists with only one element, and so on. Points will be deducted for poor design decisions and un-commented, or un-readable code as determined by your TA.

General Advice

Think beforehand about how the trie can precompute a number of the methods that you are asked to implement. By leveraging the trie more completely, you can reduce the amount of work the other methods have to do.

Also, your trie should not cause you to run out of memory unless you increase the Java heap size. Think about ways to design your trie nodes to not waste space; if you run out of heap, you are doing something wrong.