For the first part of this assignment, you will design and implement a
for storing and efficiently accessing Strings (as described in the lectures). Your
class must provide the following constructor and methods:
Trie implementation should be case-insensitive, so adding "foo" and "Foo" would
result in a single entry. You may assume that the Strings to be stored in a
consist of letters only (no spaces or puncuation marks).
As part of your
Trie class definition, you will need to define an inner class to
represent the nodes in a
Trie (similar to the
TreeNode inner classes we have previously discussed).
For extra credit, you may implement other useful
Trie methods, such as
Be sure to test your class thoroughly before moving on to part 2.
Boggle (® Hasbro) is a game in which a 4x4 grid of letters is randomly chosen, and then the players try to identify as many words in that grid as possible. Words can be formed by any sequence of adjacent letters in the grid. For example, consider the following grid.
The word "sock" is formed starting at the letter "s" in the top row, moving down diagonally to the "o", moving up diagonally to the "c", and finally moving right to the "k". Note that letters can be connected horizontally, vertically, and diagonally. The same occurrence letter may not be used more than once in the same word, however. Thus, "tot" is not a valid word in the above grid. In the real game, a player earns points for each word found in the grid, with an n-letter word earning n points. For example, "so" is worth 2 points while "strand" is worth 6 points. An invalid guess (i.e. a word not in the dictionary or not on the board) costs the player 1 point.
A BoggleBoard class has been provided
for you, along with a dictionary file named dictionary.txt.
When constructed, a
BoggleBoard reads in and stores all of the dictionary words
Trie. It then uses recursive backtracking to search the board,
containsPrefix methods to identify words from the dictionary.
Using the provided
BoggleBoard class and your own
class, design and implement a GUI-based program for playing a game of Boggle. At a
minimum, your program should generate and display the board, allow the user to
repeatedly enter words, display the valid entered words, show the player the words
at the end, and allow them to play again. For example, a very basic
interface might look like the following:
For extra credit, you may add additional functionality to the game (e.g., scorekeeping, a time limit).