Deploying a Heuristic to Prune search space in a Boggle.java Game

Question

So, I am trying to write a java program that emulates the game Boggle. It inputs two text files, the first being a text file representing the nxn board where the first line contains the dimensions of the board, i.e. a 4x4.txt file's first line will be the number 4 and the rest will be the board itself. The second txt file will be a file containing all of the possible dictionary words.

I first wanted to verify that the algorithm we use to generate all possible String outputs from an nxn grid is correct. I used a depth-first-search algorithm to do this.

I believe I've gotten this part correct. But, now I'm to implement a heuristic to help recognize dead ends and save searching through wasted words and wasting time. I am lost as to how this is supposed to go. Any help would be appreciated.

Here's the code I have thus far. Like I said, my depthFirstSearch method is correct and is giving me the right output. I am also not wedded to the TreeSet to store the dictionary words as I'm not even sure that's correct. I just did it because I knew that it was the proper ADT to store the possible String combinations.

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<String> allPossWords = new TreeSet<String>();

    public static void main(String[] args) throws Exception
    {
        Scanner dfile = new Scanner(new FileReader(args[0]));
        TreeSet<String> dictionary = new TreeSet<String>();

        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();
        }
    }

}

Answer 1

First, implement a Trie, and write a dictionary to it on initialization. Lookup time for any word is the determinstic, as the length of the word is the traversal time from the empty root of the Trie, to the final letter at a leaf.

Then, from the structure of the Trie, create a heuristic.