Design software to play a computer version of the board game Boggle. If you are unfamiliar with the game, here is a brief description: the Boggle board is a 4 4 grid onto which 16 dice are randomly placed. On the face of each die is a single letter (except for one face, which has the two letters "Qu"). The objective is to form words from sequentially adjacent cubes two cubes are considered adjacent, or neighboring, if they lie next to each other horizontally, vertically, or diagonally. Cubes in the middle of the board have eight neighbors; a cube at the corner of the board has only three neighbors. In forming a word, each cube can be used only once. The objective is to find as many words as possible in a given amount of time. In the traditional board game version, all players start at the same time, writing down as many words as they can find, and then comparing word lists when time is up. A player is awarded points for finding a word that no one else found, and more points are given for longer words. Additional details of the game are available on Wikipedia: http://en.wikipedia.org/wiki/Boggle Our computerized version has only a few modifications. We have two players: a human word finder and a computer word finder. The human goes first, and has 60 seconds to find as many words as possible. Then it is the computer's turn. As the screenshot (figure 1) suggests, the computer often trounces the human. In addition, in our version, the size of the square grid is variable, and you can play on either a 4 4 or a 5 5 board.

TestWordFinder: You are encouraged to think about testing first. Devise test cases that would help you verify that your solution correctly enforces the rules of Boggle for example, you will want cases that test whether your solution correctly recognizes that board cells cannot be reused. You will also want cases that cover common programming logic errors for example, you might make test words that use tiles near the corners to verify that your algorithm never attempts to access out of bounds indices. There are several other scenarios that you will have to think through.

public class TestWordFinder {

/** Main tester method. */

public static void main(String[] args) {

IWordOnBoardFinder myFinder = new WordOnBoardFinder();

// Here's the board that is made by makeBoard() below:

// A T R U

// S E A N

// N I O T

// B D E N

BoggleBoard board = makeBoard();

System.out.println(" Testing with following board:");

System.out.println(board);

// Make your set of test words here by appending new words

// to the two arrays below. You want to make a comprehensive

// test suite that will check your algorithm's correctness in

// the widest possible number of scenarios. The array

// positiveMatches should contain words that do occur on the

// board (and that your algorithm should therefore find). The

// array negativeMatches should contain words that do not

// occur on the board (and thus, for which, your algorithm

// should return the empty list).

String[] positiveMatches = {"reinstate"};

String[] negativeMatches = {"need"};

runTests(board, myFinder, positiveMatches, true);

runTests(board, myFinder, negativeMatches, false);

}

/* Initializes the BoggleBoard to a specific configuration.

*

* @return a specific, reproducible BoggleBoard.

*/

private static BoggleBoard makeBoard() {

// If you want to test your "Qu" functionality, simply change one of the

// letters below to a 'q'. Note that it just needs to be 'q', not 'qu'!

// The code below automatically translates a 'q' tile to a 'qu' tile

// for you.

String[] tiles = {"atru",

"sean",

"niot",

"bden"};

String[] faces = new String[tiles.length * tiles.length];

int count = 0;

for (int i = 0; i < tiles.length; i++) {

for (int j = 0; j < tiles[i].length(); j++) {

if (tiles[i].charAt(j) != 'q') {

faces[count++] = "" + tiles[i].charAt(j);

}

else {

faces[count++] = "qu";

}

}

}

return new BoggleBoard(faces);

}

/** Returns the word formed by the list of specified cells on the board.

*

* @param board the BoggleBoard object.

* @param list the list of cells which we are using to construct a word.

*

* @return the word (String) formed by using the cells in the list in order

*/

private static String getWord(BoggleBoard board, List list){

String word = "";

for (BoardCell cell : list){

word += board.getFace(cell.getRow(), cell.getCol());

}

return word;

}

/** Runs through the test cases in the given list of words.

*

* For each case, a message is printed indicating whether your method

* passed or failed.

*

* @param board the BoggleBoard on which we are playing.

* @param myFinder the word finder implementation.

* @param words the list of words to look for (or not).

* @param isPositive flag indicating whether the list of words should be

* found (i.e., positively matched) or not.

*

*/

public static void runTests(BoggleBoard board, IWordOnBoardFinder myFinder,

String[] words, boolean isPositive) {

for (String s : words) {

System.out.print("Testing with query " + s);

List list = myFinder.cellsForWord(board, s);

String word = getWord(board,list);

if (isPositive && (!s.equals(word))) {

System.out.println("...failed! Expected: [" + s

+ "], instead got: "

+ getBoardCellList(board, list));

}

else if (!isPositive && s.equals(word)) {

System.out.println("...failed! Expected: [], instead got: "

+ getBoardCellList(board, list));

}

else

System.out.println("...passed!");

}

}

/** Returns a string representation of a list of BoardCells.

*

* @param board the BoggleBoard on which we are playing.

* @param list the list of cells with which to construct a word.

*

* @return the word (String) formed by taking each of the cells in list in

* sequence.

*/

public static String getBoardCellList(BoggleBoard board,

List list) {

String retString = "[";

for (BoardCell b : list) {

retString += board.getFace(b.getRow(), b.getCol());

}

return retString + "]";

}

}