I really need help with this. I am trying to write a Boggle.java program which inputs an nxn board text file (where the first line is the integer n, the dimensions of the board) and a dictionary text file containing 172822 words. We were to first utilize a depth-first-search algorithm to compile a list of all possible strings from the given board. I have done this. But, now we're to compare the string combinations we obtained from this with the dictionary txt file words. We are to use a heuristic method to reduce the search space:

"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 that is not in the dictionary, nor is that word a prefix of any word in the dictionary."

We are also only to count matched words of length 3 or more only, too, as the dictionary text file contains only words of length 3 or more.

So, if we have the following file 4x4.txt:

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

It will match with the following words in the dictionary.txt file and output this:

aerie aeries aeriest air airest airs airt airts are ares ars arse art arts artsy arty ear ears eerie eeriest enter entera enters era ere ers erst ester ire ires kyte kytes near nearest nears nee nerts nest nester net network networks new news newsy newt ors ort owe owes own owner owners owse owsen queen queer queerest queers queries quest quester ree rees reest rei renest renew renews rent rente rentes request res resee reseen resent reset resew resewn rest ret retro rets rework reworks ria rot rote rotes row rowen rower rowers rows sea sear see seen seer sei sen sene sent sequent ser sera serai sere serene set sew sewn sky sri stere street strew strewn stria striae sty swear sweer swot tea tear teariest tears tee teen ten terai terse test tester testy tew tews tor tors torse torsk tow tower toweriest towers town townee townees tows tree treen trees tret trews tries trow trows tsk twee tween two wear wearies weariest wears wee ween weer wen went were wert west wester wet work works worse worsen worser worset worst wort wot wren wrest wries wriest wrote

Here is what i have so far (any help would be appreciated):

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

public class Boggle {

//Above main declare a static long int numWordsFormed=0; private static int numWordsFormed = 0; private static TreeSet allPossWords = new TreeSet(); public static void main(String[] args) throws Exception { Scanner dfile = new Scanner(new FileReader(args[0])); Set dictionary = new TreeSet();

while(dfile.hasNext()) { dictionary.add(dfile.next()); } dfile.close(); Scanner bfile = new Scanner(new FileReader(args[1])); int r = bfile.nextInt(); int c = r; String[][] board = new String[r][c]; for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) board[i][j] = bfile.next(); for(int row = 0; row < board.length; row++) for(int col = 0; col < board[row].length; col++) depthFirstSearch(board, row, col, ""); for(String possWords : allPossWords) System.out.println(possWords); } public static void depthFirstSearch(String[][] board, int r, int c, String word) { word = word.concat(board[r][c]); ++numWordsFormed; allPossWords.add(word); if(((r-1) >= 0) && (Character.isLowerCase(board[r-1][c].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r-1, c, word); board[r][c] = board[r][c].toLowerCase(); } if(((r-1) >= 0) && ((c+1) < board[r-1].length) && (Character.isLowerCase(board[r-1][c+1].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r-1, c+1, word); board[r][c] = board[r][c].toLowerCase(); } if(((c+1) < board[r].length) && (Character.isLowerCase(board[r][c+1].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r, c+1, word); board[r][c] = board[r][c].toLowerCase(); } if(((r+1) < board.length) && ((c+1) < board[r+1].length) && (Character.isLowerCase(board[r+1][c+1].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r+1, c+1, word); board[r][c] = board[r][c].toLowerCase(); } if(((r+1) < board.length) && (Character.isLowerCase(board[r+1][c].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r+1, c, word); board[r][c] = board[r][c].toLowerCase(); } if(((r+1) < board.length) && ((c-1) >= 0) && (Character.isLowerCase(board[r+1][c-1].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r+1, c-1, word); board[r][c] = board[r][c].toLowerCase(); } if(((c-1) >= 0) && (Character.isLowerCase(board[r][c-1].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r, c-1, word); board[r][c] = board[r][c].toLowerCase(); } if(((r-1) >= 0) && ((c-1) >= 0) && (Character.isLowerCase(board[r-1][c-1].charAt(0)))){ board[r][c] = board[r][c].toUpperCase(); depthFirstSearch(board, r-1, c-1, word); board[r][c] = board[r][c].toLowerCase(); } }