2023 SPRING 445 PROJECT #9:
THE GAME OF BOGGLE

BoggleStarter.java

EXECUTE LIKE THIS: C:\> java Boggle dictionary.txt 4x4-board.txt (any boggle file)
this is how I will test it and will expect you use args[0] as the dictionary and args[1] as the input file

ONLY WORDS OF LENGTH 3 or MORE ARE TO BE COUNTED/OUTPUTTED

ANY HEURISTIC YOU WRITE MUST BE SUB LINEAR TO THE DICTIONANRY SIZE
This means your heuristic is NOT a loop that looks at every word in the dictionary. Think binarySearch (excellent) vs sequential search (terrible)

Solving the game of Boggle can be done elegantly with recursion and backtracking. Backtracking is a technique whereby an algorithm recognizes it is impossible or unnecessary to search any deeper into the search space from a given point. An example of this is finding your way through a maze. When you hit a dead end you retreat from that point and never take the same path to that point again. A fast and efficient solution to Boggle requires a heuristic that helps you recognize a dead end and save vast amounts of wasted words formed and wasted searches (and thus vast amounts of time).

Your program is only given 10 seconds to execute on my server. To get 100% credit you must solve the 4x4 grid in the 10 sec. time allotted. If you solve the 4x4 in 10 secs or less, my script will then test your program on the 5x5 grid. If it solves the 5x5 in 5 sec. or less you get a 110% score. The 10 extra points is for the heuristic that allows you to solve a 5x5 grid very quickly. Without the heuristic the 5x5 grid takes a half hour - even on modern multi-core laptops.

Boggle is a board game that uses 16 dice arranged in a 4 x 4 grid. There is also a 5x5 version. Each die has 6 faces with a letter of the alphabet on it. Occasionally the string "Qu" will appear on a dice face. A typical board might look like this.

Here is a development strategy you should follow which verifies the string generating component algorithm first before searching the dictionary, deploying a heuristic or building a GUI.

A typical Boggle game usually starts by shaking the dice on the board thus creating a new grid of letters on the game board. The object of the game is for each player to form as many valid dictionary words as possible by connecting adjacent letters in any direction without any cycles. Think of how a King can move an a chessboard - across, up, down or diagonal. You can generate words by connecting letters in any direction as long as you don't create cycles. Thus in a 4x4 grid you could form words as long as 16 characters (well.. 17 if you hit a "Qu" dice).

DON'T JUST CODE UP THE WHOLE PROGRAM. DEVELOP IT IN STAGES. STAGE#1 IS VERIFY STRING GENERATION

The first step of your program development should be to get your DFS method to form and print/save EVERY POSSIBLE word that can be generated from the grid. Until you verify this you should not write any more code.

You will be surprised at home many unique strings  you can generate from even a 2 x 2 grid. A 2 x 2 grid can generate 64 unique strings. A 3 x 3 can generate 10,305 and a 4 x 4 generates over 12 million. A 5 x 5 generates over 115 billion. Larger grids are astronomical. There is no known closed form expression to calculate the number of strings that can be formed from an N x N grid.   The only way to calculate that number is to generate all those strings with a program and count them as you form them.

This 2x2.txt grid produces this set of unique strings ==> 2x2-64_WORDS.txt

This 3x3.txt grid produces this set of unique strings ==> 3x3-10305_WORDS.txt

This 4x4.txt grid produces 12,029,640 unique strings

This 5x5.txt grid produces 115,066,382,913 unique strings

A Heuristic:

In order to avoid forming all possible strings to find the real (dictionary) ones, you will need a heuristic to prune the search space. You must recognize that you should not bother growing/extending any word if that word is not a prefix of any existing word in the dictionary. If you search for word in the dictionary and that word is not found then you should keep using that word as a prefix to form new candidate words - if and only if that failed search word is a prefix of at least one word in the dictionary.

Here are the valid dictionary words that can be found inside the following boggle boards

The Assignment

Your program MUST produce exactly the same output my solution produces on each boggle input file. 
$ java Boggle dictionary.txt 4x4.txt
The only output is to be the real dictionary words (of length 3 or more) you found in the grid. One word per line. No other output of any kind. The words must be unique, no duplicates and they must appear in sorted order ascending from top to bottom. Please see my correct output files below and make sure your solution has the same exact words as mine.

dictionary.txt    172822 words. Your reference dictionary