This assignment is based on the classic game Boggle. In this game, players are presented with a 5x5 grid of letters (in most commercial versions, these letters are selected using dice) and are asked to within a certain amount of time find as many English-language words as they can on that grid, with the only restriction being that each letter of a word must be adjacent to all letters after it.
This (vaguely unsettling) advertisement from the 1990s illustrates the rules of the game well (https://www.youtube.com/watch?v=2shOz1ZLw4c).(Links to an external site.)
In this assignment you will combine data structures to quickly and efficiently implement the use of a canonical graph traversal algorithm to find all the words on a Boggle board.
Here is the Wikipedia page on the game (https://en.wikipedia.org/wiki/Boggle),(Links to an external site.)which might be helpful for understanding the rules.
===
BOGGLE SOLVER
===
Download the starter code.Unzip it, and then drag the contents into the src directory in a new project.
1. Write a class to read the file namedword, remove the words that start with a capital letter, and then store the remaining words in a data structure of your choice.
When choosing the data structure, think hard about what features you'll need and about the most efficient structure that gives you those features. In your code, leave a comment explaining why you chose the data structure that you chose, and the runtime and amount of space required by this data structure in terms of the number of words in the list as that number becomes large.
Feel free to either use one of Sedgewick's implementations of your preferred data structure, or one from the Java standard library. I do not recommend trying to roll your own data structures for this assignment.
2. Write a class that uses the included Boggle class to create a Boggle board, and thenuses one of the canonical graph traversal algorithmsto find all of the words from the word file that are present on the board.
At first, this problem might not look like a graph theory problem. However, it is possible to think of it in terms of graph theory. Let's treat each letter on the Boggle board as a vertex. This vertex is adjacent to the vertices that are adjacent to it on the board, including diagonally. However, there is only a valid link between a letter and the letter next to it if all the letters on the path to that new vertex form a validprefixfor a word or words in the word list. For example, "aar" would be a valid prefix, because it appears at the start of many words that appear in the list, including "aardvark" and "aardwolf, "aaz" would not be a valid prefix, because there are no words starting with those characters in our word list.
Output the board, and then all the words on the board, and then the number of words found. (see sample output files in the starter code for a reference on how the output is supposed to look.
Before you begin writing your code, send me (via email) your thoughts on what algorithm you might choose.I'll let you know if you're on the right track.