Please help me with this Java Assignment.

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. A typical board might look like this.

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 mode 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 a long as 16 characters (well.. 17 if you hit a "Qu" dice).

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 over 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 from 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.

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 forming new words that start with a word you have already searched for but failed to find if the failed search word was not a prefix of any word encountered in the search.

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

INPUT FILES TO RUN YOUR SOLUTION ON

A good solution will find all the dictionary words in the grid in under 1/4 of a second from the time the program started running till it printed out the last valid word to the screen.

Below are the input files and outputs. The outputs must match exactly. Please note that only words of lenght 3 and over should be outputted.

The reference dictionary file can be found at: http://people.cs.pitt.edu/~hoffmant/S17-401/project-10/dictionary.txt

4x4 boggle board

4qu e a in  e r et  w s to  r k y

Output for 4x4:

aerieaeriesaeriestairairestairsairtairtsarearesarsarseartartsartsyartyearearseerieeeriestenterenteraenterseraereerserstesterireireskytekytesnearnearestnearsneenertsnestnesternetnetworknetworksnewnewsnewsynewtorsortoweowesownownerownersowseowsenqueenqueerqueerestqueersqueriesquestquesterreereesreestreirenestrenewrenewsrentrenterentesrequestresreseereseenresentresetresewresewnrestretretroretsreworkreworksriarotroterotesrowrowenrowerrowersrowsseasearseeseenseerseisensenesentsequentserseraseraisereserenesetsewsewnskysristerestreetstrewstrewnstriastriaestyswearsweerswotteatearteariesttearsteeteententeraitersetesttestertestytewtewstortorstorsetorsktowtowertoweriesttowerstowntowneetowneestowstreetreentreestrettrewstriestrowtrowstsktweetweentwowearweariesweariestwearsweeweenweerwenwentwerewertwestwesterwetworkworksworseworsenworserworsetworstwortwotwrenwrestwrieswriestwrote

5x5 boggle board:

5a f b c ir k n d pz k n v we j e u bt w f j o

Output for 5x5:

arfarkboundbunbundbunkbunndipekeendewefarfenfendfeufewfubfunfundfundifundicfunkjetjeujewjobjunjunkjunketkafkefkenknewnewnewtnubpictewvendwenwendwetzek

Here is a good pseudocode outline:

FOR TESTING PURPOSES CREATE A QUICK 'n DIRTY GRID TO TEST WITH SO THAT         YOU DONT HAVE TO READ IN THE GRID FROM A FILE IN ORDER TO GET SOMETHING WORKING        THIS APPROACH WILL GERENRATE AND PRINT EVERY POSSIBLE STRING FROM THE GRID   MAIN()   {        String[][] board = { {"a","b"}, {"c,"d"} };  // 2 X 2        -or-           String[][] board = { { "a","b","c" }, { "d","e","f" }, { "g","h","i"} };  // 3 X 3        -or-           String[][] board = { { "a","b","c","d" }, { "e","f","g","h" },                                 { "i","j","k", "l"}, { "m","n","o","p" } };  // 4 X 4        for r=0 to < board.length                for c = 0 to board[r].length                        dfs( r,c,board,"");   }   private static void  dfs(int r, int c, int[][] board, String word )   {            APPEND letter at [r][c] to WORD        PRINT THE WORD         IF NORTH IS A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF NORTH, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF NORTHEAST IS A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF NORTHEAST, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF EAST IS A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF EAST, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF SOUTHEAST IS A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF SOUTHEAST, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF SOUTH IS A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF SOUTH, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF SOUTHWEST IS A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF SOUTHWEST, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF WEST IS A A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF WEST, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF NORTHWEST IS A LOWER CASE LETTER                MAKE [r][c] UPPERCASE                RECURSE PASSING IN COORDS OF NORTHWEST, BOARD AND WORD                MAKE [r][c] LOWERCASE        IF YOU MAKE IT TO HERE THERE LET IT RETURN         }