Generalize the word-search program in Chapter 10 to allow any adjacent letters (not simply those in a straight line) to be used to form a word. Thus in Figure 10.1 (on page 349), goat (starting at row 3, column 1) is now a valid word, but gag (which would reuse the g) is not. This is essentially Boggle, a popular board game. Each day, the Miami Herald has a Boggle game. A recent Boggle game is shown below. It contains such words as monkey, mule, and mouse
The puzzle file is exactly as in WordSearch.java and in fact, you can reuse most of the entire program, especially the routines to read the word and puzzle files.
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).
Next, change solvePuzzle to solveBoggle as follows:
/** * 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( new Position( 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: