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.
The input file is exactly as in WordSearch.java and in fact, you can reuse almost the entire program, especially the routines to read the word and puzzle files. In order to limit the amount of output, for this assignment, words that are less than nine characters are not to be considered matches.
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.
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: