Lab 9: Word Search

Learning Outcomes

Overview

This assignment was inspired by the Boggle board game originally distributed by Parker Brothers. A 4-by-4 grid of letters is presented to players who generate a list of words that can be constructed by combining adjacent letters in the grid. No grid position can be used twice in the same word. After a timed round, each player receives a certain number of points (based on the length of the word) for each unique word in their list.

In this assignment, you will create a program that will take a grid of letters and a list of words to produce a list of all of the words in the list that can be constructed by joining adjacent letters in the grid.

You are required to implement the recursive algorithm, recursiveSearch() method in the GameBoard class (more details later). This method implements the core recursive algorithm that generates all possible letter combinations on the game board and finds all of the letter combinations that are found in a dictionary (specified by a file containing a list of words). There are two variations of the recursive search that could be implemented: 4-way and 8-way. You are required to implement the 4-way search and the 8-way search.

The 4-way search considers only the game pieces to the North, South, East, and West as neighbors. The 8-way search includes the additional game pieces to the NW, NE, SW, and SE as neighbors as well.

For simplicity, let's consider the 4-way search on the game board below first. Here LEAP is a legal letter combination since L is to the West of E, which is to the West of A, which is to the North of P. However, APE is not a legal letter combination because E is not a N, S, E, or W neighbor of P.

U L E A
A O A P
F R O P
H V K T

Now consider the 8-way search. The colored text in the following sample game board demonstrates legal letter combinations for LOOT, APE, and ROPE, but the letters that formed ROPE may not be used to form PORE since R and E are not adjacent to one another. Also note that ROAR is not possible since you cannot use the R twice in the same word.

U L E A
A O A P
F R O P
H V K T
U L E A
A O A P
F R O P
H V K T

Implementation

GameBoard Class

You must implement a class called GameBoard that will manage the grid of letters. Each GameBoard object must maintain the following data:

The GameBoard class must implement the following methods:

recursiveSearch() Details

The recursiveSearch() method will need to make, at most, eight recursive calls — on call to each neighbor (NW, N, NE, W, E, SW, S, and SE). It should not make the recursive call if the neighbor has already been visited or such a call is for an invalid row or column.

The recursion algorithm must be structured such that words with fewer than 3 characters or more than 15 characters should not be considered.

GameBoard.Cell Class

The Cell class is used to model a letter in the grid. It stores the row, column, and letter of the grid cell and provides functionality that allows Cell objects to be stored in hashing-based data structures.

Word Search Command Line Interface

You must implement the WordSearchCLI class. The class must provide a program with a command line interface that accepts four arguments:

The program must produce the following output to the console (in this order):

Benchmarking

You must include sample results running your program as follows:

In addition, you must experiment with the different strategies and grid sizes (including making your own larger grid files, if appropriate) in order to characterize the completion time differences between the various strategies. You should prepare a Word document report that describes the rationale for the trial runs you performed, includes the benchmarking results of your tests, and summarizes your conclusions. Be sure to add it to your repo, commit it, and push it to GitHub.

Exception Handling

Your program must handle any exceptions in a reasonable way.

Just For Fun

Once you have completed the requirements, you may choose to do any or all of the following:

See your professor's instructions for details on submission guidelines and due dates.

Acknowledgements

This assignment was originally developed by Dr. Chris Taylor and Dr. RJ Nowling.

Note: Word lists contain lowercase letters while the grids contain uppercase