CSCI 151 - Lab 9 - Spring 2008 Boggle Solver

11:59.59pm, Sunday, April 27

In today's lab you'll implement a portion of the Set interface using the Trie data structure. You can refer to these lecture notes for details on the use and implementation of Tries.

Part 1 - Finding Words on a Boggle Board

In the game of Boggle, a player is presented with a 4x4 grid of squares, each one holding a letter of the alphabet, as shown below:

The object of the game is to find as many words as possible on the board, formed from the letters in the squares. A word is formed by following a path from square to adjacent square, going horizontally, vertically, or diagonally, without using the same square more than once. For example, the word "MURALS" can be found in the grid as shown below:

Your job is to write a program which finds all the words in a given Boggle board. Your program will have two command-line arguments. The first is the name of a file containing a lexicon of words in the English language. The second is the name of a file containing a Boggle board. The board file has four lines, with four letters per line. The output of the program should be a list of the words found on the board.

NOTE: Treat the letter "Q" as "Qu" for our purposes.

The algorithm

A nice algorithm, based on recursive backtracking, can be written which uses a trie to find all the words on the board.

let lextree = a trie containing all the words in the lexicon.

let wordset = a set in which to save all found words.  (You can
use a Trie for this, too.)

for each square sq in the grid {
  search for words starting at sq in lextree;
}

The search method uses the following logic:

search(Square sq, String sofar, ...) {

  // check to see if we have found a word on the current path

  if the current path represents a word in the dictionary

    add the word to the wordlist;

  // continue searching on all possible paths from this square

  let l = the letter in sq;

  for each unmarked square sq' adjacent to sq {

    mark it;

    search for words starting at sq' in trie.child[l];

    unmark it;

  }

}

Notes:

Choosing the correct parameter list for the search method is very important. You need at least:
- An (x,y) pair representing a board position. Use either two ints or a java.awt.Point object.
- A String representing the letters on the path taken so far.
A good way to set up the loop in the recursive search method is to create a list of all the unmarked adjacent squares and then step through it with an Iterator or a foreach loop.
You may use my version of Trie for completion of this part of the lab. Trie has the following methods:

Trie()
A no-argument construtor which creates an empty trie; that is, one containing no strings.
boolean containsEmptyString()
Returns true if and only if the trie contains the empty string. (This method just returns the isWord flag in the root of the Trie.)
boolean contains(String string)
Returns true if the trie contains the given string, false otherwise. (You won't need this method for the Boggle application, so I've disabled it in my version.)
boolean add(String string)
Inserts string in the trie, if it is not already present. Returns true if and only if the trie is modified by this operation; that is, if string was not already in the Trie.
boolean isEmpty()
Returns true if the trie contains no strings, false otherwise.
Trie getChild(int n)
Returns the nth subtrie of the given trie; that is, the one representing the letter ('a' + n). If the nth subtrie is empty, this method returns null.
String toString()
Returns a string representation of the list of strings contained in the trie.
The lab9.jar file contains my Trie.class, board.txt (a sample Boggle board), lexicon.txt (the dictionary), and a file with a smaller word list called small.txt.

Part 2 - Writing your own version of the Trie class

Write your own version of the Trie class as a subclass of AbstractSet<String>. Define the data members of Trie as follows:

    boolean isWord;

    Trie[]  children;

The no-argument constructor for a Trie should initialize an empty Trie. The result should be a single Trie node whose isWord flag is false and whose children array is an array of null pointers. (You need to instantiate the array, but not its individual entries.) Recall that the size of the array is determined by the number of characters in the alphabet; in our case, that will be 26. (This is a good place for the use of a "static final" variable to define a constant, so that you don't need to hard-code the number 26 in more than one place in your program.)

You are responsible for implementing the following methods in Trie.java:

boolean containsEmptyString(): Returns true if and only if the trie contains the empty string. (This method just returns the isWord flag in the root of the Trie.)
boolean contains(String string): Returns true if the trie contains the given string, false otherwise.
boolean add(String string): Inserts string in the trie, if it is not already present. Returns true if and only if the trie is modified by this operation.
boolean isEmpty(): Returns true if the trie contains no strings, false otherwise.
Trie getChild(int n): Returns the nth subtrie of the given trie; that is, the one representing the letter ('a' + n). If the nth subtrie is empty, this method returns null.
String toString(): Returns a string representation of the set of strings contained in the trie.; Hint: Write a private method List<String> toList(); which returns a List of strings contained in the trie in alphabetical order, as described below. Then call the toString method of the List.
private List<String> toList(): Returns a List of strings containing all the strings in the trie, in lexicographic (alphabetical) order. Use either a LinkedList or an ArrayList. (Hint: Use a recursive helper method with a prefix string as an argument.)
Iterator<String> iterator(): Create a factor method which genereates an iterator over all the string in the trie. (Hint: Lists have an iterator() method that produces what you need!)

You'll get an error message if you don't also write a size method, which is abstract in AbstractSet. Try writing one, but if you don't have time, just write a method that returns 0. You shouldn't need a working size method for the Boggle application.

Notes:

You need to be able to break a String down into its individual characters. You can use the charAt(int) method in String for this.
In searching a trie for a string, the individual characters of the string must be used to index into each trie node's array of children. To accomplish this, you will need to convert each character to a numeric index. In particular, you will need to convert 'a' to 0, 'b' to 1, 'c' to 2, ..., and 'z' to 25.

This is easy to do in Java, because characters are considered to be a numeric type compatible with int, so it is possible to perform arithmetic operations on them. When Java performs arithmetic on characters, each character is interpreted as the number used in its Unicode representation. Because the letters of the alphabet are assigned consecutive Unicode values, a letter can be converted to a number in the range 0..25 by simply subtracting the letter 'a' from it. For example, 'b' - 'a' is equal to 1, 'c' - 'a' is equal to 2, 'd' - 'a' is equal to 3, etc.
What will happen if the user tries to add a string containing a character outside the range 'a'..'z'? It is likely that an "index out of bounds" exception will occur in the add method. Your program should handle this exception somehow, either in the Trie class or in the application programs you will write which use it.
You should test your Trie class before trying it out with the Boggle application. Here's a suggested test application:

The program has one or more command-line arguments. The first argument is a file name containing a lexicon or word list. The remaining arguments are words to be searched for. The program builds a trie from the lexicon, and then displays it using toString. Then it uses the contains method to test all of the search words and print each one that is found, one per line.

Here is another board just for you!

Roll Again

What to Hand In

Use handin to submit the following files:

All .java files necessary for compiling your code (including those from previous labs)
A README file with:
1. Your name
2. Any known problems or interesting design decisions that you made
3. The honor code

Last Modified: April 20, 2008 - Benjamin A. Kuperman