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 word must be at least three letters long.
• Letters in the word must be connected horizontally, vertically, or diagonally.
• Each letter may be used only once in a given word.

• Implement Tries data structure.
• Implement Backtracking search algorithm.
• Gain a deeper understanding of object-oriented programming in Java.

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

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

You FTP the following java files

• DictionaryTrie.java

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

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.

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.

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.

LRYTTE  VTHRWE  EGHWNE  SEOTIS
ANAEEG  IDSYTT  OATTOW  MTOICU
AFPKFS  XLDERI  HCPOAS  ENSIEU
YLDEVR  ZNRNHL  NMIQHU  OBBAOJ

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.

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.