Assignment #4: Boggle

Covers

Recursion, backtracking, java.util classes such as Lists and Maps.

Basic problem

Write a program to solve Boggle, a popular board game. Each day, the Miami Herald has a Boggle game. In boggle, you form words by using adjacent characters. You may not reuse a character in a given position to form a word, though repeated characters in different positions can be used. A recent Boggle game is shown below. It contains such words as memo, monkey, mule, and mouse


The Input and Output

The puzzle file is a two dimensional array of characters.

The dictionary of valid words is dict.txt, with the usual disclaimer that it is not my dictionary and may have some inappropriate words. It is too large to manually screen.

Your output should list each word found, along with the number of points it is worth (see the image above), the location where the characters in the word can be found, and the total number of points. If the number of words exceeds 200, you don't have to print them all out. Instead, print out only the words of length eight or more, and a summary of how many words of each length 3-7 there are (and the number of points they account for).

Strategy

First, provide a Position class to store a row and column as a pair, and provide a constructor, toString, and equals (hashCode would also be good to have, but is not needed). Make sure Position is an immutable type. Be very careful to make sure that the equals method in Position takes an Object as its parameter. Otherwise, calling contains on a List of Position objects will not work.

Next, the basic recursive login would be something along the lines of the following (note you should use fully typed collections, such as Map<String,List<Position>>): 

    /**
     * Routine to solve the Boggle game.
     * @return a Map containing the strings as keys, and the positions used
     *     to form the string (as a List) as values
     */
    public Map solveBoggle( )
    {
        Map results = new HashMap( );
        List path = new ArrayList( );

        for( int r = 0; r < rows; r++ )
            for( int c = 0; c < columns; c++ )
            {
                solve( newPosition( r, c ), "", path, results );
            }

        return results;
    }
Observe that solveBoggle calls the routine solve for each position in the grid. solve is recursive, and implementing it is virtually the entire assignment. After you implement solve you should have a routine that can print out, in a nice form, the Map returned by solveBoggle, to meet the output specifications above.

The specification for the recursive solve routine is: 

    /**
     * Hidden recursive routine.
     * @param thisPos the current position
     * @param charSequence the characters in the potential matching string thusfar
     * @param path the List of positions used to form the potential matching string thusfar
     * @param results the Map that contains the strings that have been found as keys
     *       and the positions used to form the string (as a List) as values.
     */
    private void solve( Position thisPos, String charSequence, List path, Map results )
    {
        /* Less than one page of code will do it. */
    }
In implementing solve you will want to do the following:
  1. Attach the character at thisPos to charSequence.
  2. If the resulting current string is not a prefix of any word in the dictionary, you can return. To do this test, store the dictionary as a simple sorted array, and use java.util.Arrays.binarySearch.
  3. Otherwise, you will want to update the path variable, and look for some matches.
  4. If the current string is a word in the dictionary you want to update the map.
  5. In any event, you want to recursively call solve with appropriate parameters, on all adjacent positions, skipping those that have already been used in the current string, and being careful not to wander off the end of the board.
  6. Don't forget to update the path variable when you return from solve.

Copying and Cloning

As much as possible, you should avoid making copies of variables. In particular, the last two parameters to solve (the List and Map) are to be the same object for each unique invocation of solveBoggle. YOU MAY NOT MOVE THEM TO BE CLASS VARIABLES. However, what this means is that when you put a String as a key and a List as a value into the Map, you will need at that point to make a copy of the List, since otherwise the Map would simply be storing lots of references to the same single list (which would be empty at the end of the program). You can use any of the List (subclasses) constructors to create a List from another List.

What To Submit

Submit complete source code and run your program on the word puzzles from the Herald that I will post.