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, output the total number of words of each length that you find (in other words, the number of words of length 2, length 3, and so on), and also output ALL words, with their positions that are length nine characters or more.
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<String,List<Position>> solveBoggle( ) { Map<String,List<Position>> results = new HashMap<String,List<Position>>( ); List<Position> path = new ArrayList<Position>( ); 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<Position> path, Map<String,List<Position>> results ) { /* Less than one page of code will do it. */ }In implementing solve you will want to do the following: