[Solved]Java Boggle Assignment Execute Like C Java Boggle Dictionarytxt 4×4 Boardtxt Boggle File U Q37285695

Java Boggle Assignment

EXECUTE LIKE THIS: C:> java Boggledictionary.txt 4×4-board.txt (orany boggle file)
Use args[0] for the dictionary and args[1] as the input file

The output you produce must match exactly and in same order tothe 191 words HERE

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

ANY HEURISTIC YOU WRITE MUST BE SUB LINEAR COMPLEXITY W/RESPECTTO N, THE DICTIONARY SIZE
This means your heuristic is NOT a loop that looks at everyword in the dictionary. Think binarySearch (excellent) vssequential search (terrible)

Solving the game of Boggle can be done elegantly with recursionand backtracking. The solution code is almost identical to theSwamp program you wrote.

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

Here is a development strategy you should follow which verifiesthe string generating component algorithm first before searchingthe dictionary.

A typical Boggle game usually starts by shaking the dice on theboard thus creating a new grid of letters on the game board. Theobject of the game is for each player to form as many validdictionary words as possible by connecting adjacent letters in anydirection without any cycles. Think of how a King can move an achessboard – across, up, down or diagonal. You can generate wordsby connecting letters in any direction as long as you don’t createcycles. Thus in a 4×4 grid you could form words as long as 16characters (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 yourDFS method to form and print/save EVERY POSSIBLE word that can begenerated from the grid. Until you verify this you should not writeany more code.

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

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

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

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

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

Here are the valid dictionary words that your boggle programshould output on the 4×4-board.txt input:

• 4×4-board.txt ==> 4×4-board-matches.txt exactly 191words

The Assignment

Your program MUST produce exactly the same output mysolution produces on the input file.

$ java Boggle dictionary.txt 4×4-board.txt

The only output is to be the real dictionary words (of length 3or more) you found in the grid. One word per line. No other outputof any kind. The words must be unique, no duplicates andthey must appear in sorted order ascending from top tobottom. Please see my correct output files below and makesure your solution has the same exact words as mine.

Boggle.java starter file:

import java.io.*;
import java.util.*;

// just generates all the strings & prints them as they aregenerated

public class Boggle
{  
   static String[][] board;
   static long startTime,endTime; // for timing
   static final long MILLISEC_PER_SEC = 1000;

   public static void main( String args[] ) throwsException
   {   startTime=System.currentTimeMillis();
       board = loadBoard( args[1] );
      
       for (int row = 0; row <board.length; row++)
           for (int col =0; col < board[row].length; col++)
              dfs( row, col, “” ); // FOR EACH [R][C] THE WORDSTARTS EMPTY
      
  
       // EVENTUALLY YOU ADD HERE
       // PRINT OUT YOUR SORTED HITSCONTAINER ONE WORD PER LINE
      
       endTime =System.currentTimeMillis(); // for timing
       System.out.println(“GENERATIONCOMPLETED: runtime=” + (endTime-startTime)/MILLISEC_PER_SEC);
      
   } // END MAIN—————————————————————————-

   // IF THIS REMINDS YOU OF THE SWAMP THEN YOU AREGETTING IT!
  
   static void dfs( int r, int c, String word )
   {  
       word += board[r][c];
       System.out.println( word ); //EVENTUALLY REPLACE WITH IF FOUND IN DICT ADD TO HITSCONTAINER
      
       // THIS IS THE FORM OF EACH OF YOURN,NE,E,SE,S,SW,W,NW BLOCKS
      
       // IM GIVING THE NORTH VERSION -YOU MUST WRITE 7 MORE BELOW IT
       // DO NOT ELSE THEM OFF GIVE EVERYBLOCK AN INDEPENDENT IF TEST
       // YOU WANT TO RESUME YOURCLOCKWISE SWEEP OF HTE NEGHBORS
      
       // NORTH IS [r-1][c]
      
      
      
       if ( r-1 >= 0 &&board[r-1][c] != null ) // THE r-1 WILL CHANGE FOR EVEY BLOCKBELOW
       {   String unMarked =board[r][c]; // SAVE TO RESTORE AFTER RET FROM RECURSION
           board[r][c] =null; // // null IS THE MARKER OF A VALUE AS IN USE ALREADY
           dfs( r-1, c,word ); // THE r-1,c WILL CHANGE WITH EVERY OTHER BLOCK BELOW
           board[r][c] =unMarked; // BACK. UNMARK IT
       }
      
       // NE IS [r-1][c+1] YOU WILL NEEDTO TEST BOTH r-1 AND c+1 FOR OUT OF BOUNDS
      
       // E IS [r][c+1]
      
       // SE IS …
      
       // S IS …
      
       // SW IS …
      
       // W IS …
      
       // NW IS …
      
   } // END DFS—————————————————————————-

  //=======================================================================================
   static String[][] loadBoard( String fileName ) throwsException
   {   Scanner infile = new Scanner( newFile(fileName) );
       int rows = infile.nextInt();
       int cols = rows;
       String[][] board = newString[rows][cols];
       for (int r=0; r<rows; r++)
           for (int c=0;c<cols; c++)
              board[r][c] = infile.next();
       infile.close();
       return board;
   } //END LOADBOARD

} // END BOGGLE CLASS

Development Strategy:

HERE IS A SKETCH OF HOW TO DO WRITE JUST ENOUGH TO VERIFY YOU ARE CORRECTLY GENERATINGALL POSSIBLE WORDS FROM THE BOGGLE GRID.Above main declare a static long int numWordsFormed=0;and you can declare your board there tooString[][] board;In main do similar to swamp except instead of a single call to dfs board = loadBoard(..) or something like this // starting with EVERY letter of board, form all strings from it for every cell [r,c] in the boggle board call DFS(r,c, “”); println numWordsFormed;Below main write your DFS that only forms and counts wordsformed. Don’t search dictionary or do hueristics until you have verified correctness of the words/count generated.DFS( , int r, int c, String word ){ tack the letter at [r][c] onto the end of your incoming word println( word ); // you wont want to do this for grids >= 4 ++numWordsFormed; if NORTH’s indices [r-1][c] are not out of bounds AND letter at [r-1][c] is unmarked mark the letter at r,c recurse passing in coords of N (relative to current r,c and the word ) unmark letter at r,c if NE … if E … if SE … if S … if SW … if W … if NW …}

4×4 text:

4qu e a in e r et w s to r k yOER S NOL T Show transcribed image text OER S NOL T

Expert Answer

---

Answer to Java Boggle Assignment EXECUTE LIKE THIS: C:> java Boggle dictionary.txt 4×4-board.txt (or any boggle file) Use args[0]… . . .