Problem Description:

In this assignment, you will implement a version of a word search game much like Boggle1 and other popular word games. The approach you take to finding words on the board will be a direct application of depth-first search with backtracking. The version of the game that you will implement is played on a square board according to the following rules. 1. Each position on the board contains one or more uppercase letters. 2. Words are formed by joining the contents of adjacent positions on the board. 3. Positions may be joined horizontally, vertically, or diagonally, and the board does not wrap around. 4. No position on the board may be used more than once within any one word. 5. A specified minimum word length (number of letters) is required for all valid words. 6. A specified lexicon is used to define the set of all legal words.

Implementation Details:

Your must implement your solution to the assignment in terms of two provided files: WordSearchGame.java and WordSearchGameFactory.java, plus one class that you create from scratch all on your own. The interface WordSearchGame describes all the behavior that is necessary to play the game. So, we can think of this interface as the specification for a game engine. You must develop your own game engine that meets this specification; that is, you must write a class that implements the WordSearchGame interface. You can name this class anything you want and you can add as many additional methods as you like. The WordSearchGameFactory is a class with a single factory method for creating game engines. You must modify the createGame method to return an instance of your class that implements the WordSearchGame interface. Factory classes like this are convenient ways of completely separating an implementation (your class) from a specification (the provided interface). So, the test suite used for grading can be written completely in terms of the interface and without any knowledge of the specific classes used in the implementation. A brief example client along with the corresponding output are given below. Although the class that implements the WordSearchGame interface must be in the same directory, the ExampleGameClient code is independent of its name or any other details of the class.

Given Code for WordSearchGame.java

import java.util.List; import java.util.Set; import java.util.SortedSet;

/** * Defines the methods needed to play a word search game. * * @author Dean Hendrix (dh@auburn.edu) * @version 2018-03-22 * */ public interface WordSearchGame { /** * Loads the lexicon into a data structure for later use. * * @param fileName A string containing the name of the file to be opened. * @throws IllegalArgumentException if fileName is null * @throws IllegalArgumentException if fileName cannot be opened. */ void loadLexicon(String fileName); /** * Stores the incoming array of Strings in a data structure that will make * it convenient to find words. * * @param letterArray This array of length N^2 stores the contents of the * game board in row-major order. Thus, index 0 stores the contents of board * position (0,0) and index length-1 stores the contents of board position * (N-1,N-1). Note that the board must be square and that the strings inside * may be longer than one character. * @throws IllegalArgumentException if letterArray is null, or is not * square. */ void setBoard(String[] letterArray); /** * Creates a String representation of the board, suitable for printing to * standard out. Note that this method can always be called since * implementing classes should have a default board. */ String getBoard(); /** * Retrieves all valid words on the game board, according to the stated game * rules. * * @param minimumWordLength The minimum allowed length (i.e., number of * characters) for any word found on the board. * @return java.util.SortedSet which contains all the words of minimum length * found on the game board and in the lexicon. * @throws IllegalArgumentException if minimumWordLength < 1 * @throws IllegalStateException if loadLexicon has not been called. */ SortedSet getAllValidWords(int minimumWordLength); /** * Computes the cummulative score for the scorable words in the given set. * To be scorable, a word must (1) have at least the minimum number of characters, * (2) be in the lexicon, and (3) be on the board. Each scorable word is * awarded one point for the minimum number of characters, and one point for * each character beyond the minimum number. * * @param words The set of words that are to be scored. * @param minimumWordLength The minimum number of characters required per word * @return the cummulative score of all scorable words in the set * @throws IllegalArgumentException if minimumWordLength < 1 * @throws IllegalStateException if loadLexicon has not been called. */ int getScoreForWords(SortedSet words, int minimumWordLength); /** * Determines if the given word is in the lexicon. * * @param wordToCheck The word to validate * @return true if wordToCheck appears in lexicon, false otherwise. * @throws IllegalArgumentException if wordToCheck is null. * @throws IllegalStateException if loadLexicon has not been called. */ boolean isValidWord(String wordToCheck); /** * Determines if there is at least one word in the lexicon with the * given prefix. * * @param prefixToCheck The prefix to validate * @return true if prefixToCheck appears in lexicon, false otherwise. * @throws IllegalArgumentException if prefixToCheck is null. * @throws IllegalStateException if loadLexicon has not been called. */ boolean isValidPrefix(String prefixToCheck); /** * Determines if the given word is in on the game board. If so, it returns * the path that makes up the word. * @param wordToCheck The word to validate * @return java.util.List containing java.lang.Integer objects with the path * that makes up the word on the game board. If word is not on the game * board, return an empty list. Positions on the board are numbered from zero * top to bottom, left to right (i.e., in row-major order). Thus, on an NxN * board, the upper left position is numbered 0 and the lower right position * is numbered N^2 - 1. * @throws IllegalArgumentException if wordToCheck is null. * @throws IllegalStateException if loadLexicon has not been called. */ List isOnBoard(String wordToCheck);

}