Your WordOnBoardFinder class must implement the cellsForWord method of the IWordOnBoardFinder interface. This method is responsible for finding whether (and where) a given word occurs on the board. It is recommended that you follow the public/private approach create private helper method (give it a descriptive name!) that is called from within cellsForWord. This helper method should be recursive. It will search for the word beginning at a specified (row, column) cell on the board. The code in the method cellsForWord should call the helper method with every possible (row, column) as a starting point as follows:

import java.util.*;

/** ADD ME! */

public class WordOnBoardFinder implements IWordOnBoardFinder {

public List cellsForWord(BoggleBoard board, String word) {

// IMPLEMENT ME!!

// Looks in the Boggle board and figures out the board cells needed

// to construct a given word, using a recursive procedure.

// The method documentation (in the interface) provides additional details.

// For now, we simply return an empty list. Thus, the program

// will not be able to validate any of the words keyed in by

// the human player. Replace the following return statement

// once you finish method definition.

List list = new ArrayList();

for(int r = 0; r < board.size(); r++) {

for(int c = 0; c < board.size(); c++){

if (helper(board, r, c, list, ...)) {

// not shown

You are free to write the helper method as you see fit. Here are some suggestions. The goal of the helper method is to recursively "grow" a match to the word, one letter/cell at a time. At any given point in time, it will have a partial match to the word (say, the first k characters) and it will be trying to extend that match by matching the next character in the word with its current position (row, column) on the board. You may want the helper method to have an int parameter which can act as an index indicating which character in the string is the one being tentatively matched to the current board cell. The first time the helper method is called, this parameter will have the value zero, indicating that the first character of the string should be matched. There are several things to keep in mind: When should you stop making recursive calls? There are two cases: you have found the word (how do you check this?) or, given the tentative match you have so far, it is not possible to extend the match (why not?). Which direction can you move to extend the match? A board cell has between three and eight neighbors, depending on its location on the board. It might be helpful to have a separate method that takes care of the messiness of figuring out where you can move next. Depending on how you do it, this method might return a boolean (valid/invalid move) or a list of neighboring cells. A board cell can be matched only once. If a word contains more than one occurrence of a given letter, how will you prevent a cell from being accidentally re-used? When you don't find the word you are looking for, you'll have to backtrack and undo the work done so far. As with typical recursive backtracking code, this involves undoing the one step made before the recursive invocation(s). What changes are you making at each step? What do you need to undo? Be careful when finding a word that contains "qu" because in this case, two letters in the word are matched to a single cube on the Boggle board (the "Qu" cube).A good plan is to first get your program working for non-Q words and then deal with this special case at the end. When you are done, you can use your TestWordFinder class to verify that your recursive solution works just compile and run TestWordFinder.java. Further, you may wish to modify the makeBoard method in TestWordFinder when you are ready to test your logic for handling the "qu" case.