Assignment 6

Computer Science 132: Analysis of Algorithms

Assignment 6

The code for this lab is due Thursday December 10 before 23:00

Boggle is a word game where players look for words in a 4 by 4 grid of letters. Words in the grid may be formed by connecting adjacent letters provided that a letter is not used twice in the word. For example, given the following grid:


a h f p
b e f c
t j g k
o h r u

the following valid words may be formed: bet, beg, rug, jet, get, urge. Note that "tot" is not a valid entry because it uses the 't' cell twice.

Your assignment is to write a program that creates and displays a boggle board, allows a player to enter words, and scores the player's performance by checking if each entered word is valid. The player receives 1 point for each letter in a valid word and -1 if the word is not valid. When the player has finished entering words, the program should display the player's score and all valid words that the player did not find.

In completing this assignment, you should make use of the Trie class (already defined and implemented), the LetterCell class (defined and implemented), and the Board class (defined but not yet implemented). Briefly, here are descriptions of these classes and how you will used them. More information is available in their header files (available in ~miller/cs231/hw6).

Trie class -- stores a list of words and allows for a very efficient means of inserting, finding, deleting, and checking for prefixes. An object of this class should store your dictionary. Additional objects can also store words found by the program or entered by the player.
LetterCell -- holds one letter. It also maintains a list of pointers to neighboring cells.
Board -- maintains a grid of letter cells. Its constructor creates LetterCell objects and builds the neighbor lists for its LetterCell objects. Since the Board class needs access to private LetterCell data fields, it is a "friend" of the LetterCell class.

Your first task is to implement the Board class, of which the constructor is the most challenging. Because many things could go wrong, it is imperative to test your implementation before you go on to implement the Boggle game. The file Test.cpp is a test driver for the Board class, which you should study and use to implement your Board class.

Once you have the Board class implemented and tested, you can implement the Boggle game. Here the most challenging part is to write the code that searches for all valid words in the letter grid. This search is accomplished using the backtracking approach. Pruning is accomplished by not pursuing prefixes that have no words in the dictionary. To make sure that letter cells are not used more than once, member functions for the LetterCell class are provided that allow the search to mark and unmark its objects.

A make file is provided that creates two programs: testboard (compiled from Test.cpp) and boggle (compiled from Boggle.cpp). To make testboard, type "make testboard" at the unix prompt. To make boggle, type "make boggle" at the prompt.

A small dictionary file called "words" is located in the hw6 directory.