Java Boggle Solver:

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 mark that last step as a dead end and avoid going down that path. A fast and efficient solution to Boggle requires a hueristic that helps you recognize a dead end and save vast amounts of wasted searches (and thus vast amounts of time).

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.

The Assignment

Your program MUST produce exactly the same output my solution produces on each boggle input file. You are to hard code the dictionary.txt filename somewhere inside your program and always load that file as your dictionary of legal words. For this assignment there is only one dictionary file we will ever use. So, go ahead and hard code the "dictionary.txt" filename in your code. Your program should be executed as follows:

$ java Boggle 4x4-board.txt 

The only output is to be the real dictionary words 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

The BoggleBoard will be generated from an input file, structured as follows: (4x4-Board.txt)

4 qu e a i n e r e t w s t o r k y 

Only words of length 3 or more are to be outputted