Boggle Solver Depth First Searching Issues
<p>I am working on an assignment which concerns creating a Boggle Solver program. I have the following four classes: Boggle.java, BoggleDictionary.java, BoggleBoard.java, and LetterDie.java.</p>

<p>I know that a more efficient way would be to use a Trie but I spoke to my professor and he said that I could use that as but I'm going to focus on finishing this part then try to create a solver using a Trie.</p>

<p>My main issue is on Boggle.java. The Depth First Search is only returning the letters of the 2D Array/ NxN matrix, in their respective order. I have however, included another file Test.java that has a specified board set up as well as a dictionary containing words that I could finding on the board, for testing purposes, and the DFS works perfectly fine. If anyone could assist me with spotting the error in the Boggle.java I would greatly appreciate it.</p>

<p><strong>Boggle.Java</strong></p>

<pre><code>/**
* Boggle.java. Implements a Boggle game engine.
*
* @author    
*   @author   
*   @version  2012-11-06
*
*/

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

public class Boggle {

// the Boggle game board
  private BoggleBoard board;
// game dictionary
  private BoggleDictionary dictionary;


  ArrayList&lt;String&gt; userList = new ArrayList&lt;String&gt;();
  ArrayList&lt;String&gt; machineList = new ArrayList&lt;String&gt;();
  private String newDictionary;
  private String[][] newBoard;
  String userWords;
  public static final int MINIMUM_WORD_LENGTH = 3;
  int userCount = 0;
  boolean visited[][] = new boolean[4][4];
  int machineCount = 0;
  Stack&lt;String&gt; stack;
  String wordSoFar = "";
  Scanner userInput = new Scanner(System.in);

// other fields as necessary ...
// You must fill this in.

/**
* Initializes the game to use a random board
* and default dictionary.
*/
  public Boggle()throws FileNotFoundException
  {
  // setup board
     board = new BoggleBoard();
  // setup dictionary
     dictionary = new BoggleDictionary();
  // other stuff ...
  // You must fill this in.
  }

/**
 * Initializes the game to use the specified board
 * and the specified dictionary.
 */
  public Boggle(BoggleBoard b, BoggleDictionary d) throws FileNotFoundException {

     b = new BoggleBoard(newBoard);
     //change these to use the specified board/dictionary methods.
     d = new BoggleDictionary(newDictionary);
  }  

/**
 * Play the game.
 */
  public void play() {

  // DO NOT MODIFY THIS METHOD

     System.out.println("/ / / / / / / / / /");
     System.out.println("Let's play Boggle!\n");

     System.out.println("The board: ");
     displayBoard();
     System.out.println();

     System.out.println("Your turn: ");
     System.out.println("-------------------");
     userTurn();
     System.out.println();

     System.out.println("My turn: ");
     System.out.println("-------------------");
     machineTurn();
     System.out.println();

     System.out.println("The results: ");
     System.out.println("-------------------");
     reportResults();
     System.out.println();
     System.out.println("/ / / / / / / / / /");
  }

/**
 * Play the user's turn.
 */   
  public void userTurn() 
  {
     System.out.println("Please enter your guesses followed by a space. " + 
        "If you would like to end the game"
        + " please press *.");
     do
     {
        userWords = userInput.next();
        getUserWords();
     }
     while (!userWords.equals("*"));
     ArrayList&lt;String&gt; userwords = getUserWords();
  }

/**
* Play the machine's turn.
*/
  public void machineTurn() 
  {
     for (int i = 0; i &lt; 4; i++)
     {
        for (int j = 0; j &lt; 4; j++)
           depthFirstSearch("", i, j);
     }
  }

  private void depthFirstSearch(String prefix, int row, int col) 
  {
    // make sure its a valid point
     if (row &lt; 0 || col &lt; 0 || row &gt;= 4 || col &gt;= 4)//board.size() || col &gt;= board.size()) 
        return;
    // can't visited a cell more than once
     if (visited[row][col]) 
        return;

    // not allowed to reuse a letter
     visited[row][col] = true;

  //check to see if the word is valid.  
     prefix = prefix + BoggleBoard.board[row][col]; 
     if (dictionary.contains(prefix))
     {
        System.out.println(prefix);
     }

    // consider all neighbors
     for (int ii = -1; ii &lt;= 1; ii++)
        for (int jj = -1; jj &lt;= 1; jj++)
           depthFirstSearch(prefix, row + ii, col + jj);

     visited[row][col] = false;
  }

/**
* Display the game results.
*/  
  public void reportResults() {

  // You must fill this in, but you can only add to the println arguments
  // in the following lines.

     System.out.println ("Number of user words: " + userCount);
     System.out.println ("User score: ");
     System.out.println ("Number of machine words: " + machineCount);
     for (int i = 0; i &lt; machineList.size(); i++)
     {
        System.out.println(machineList.get(i));
     }
     System.out.println ("Machine score: ");

  }  

/**
* Print the board to standard out.
*/   
  public void displayBoard() {

  // DO NOT MODIFY THIS METHOD

     System.out.println(board);
  }

/**
* Return a list of valid words identified by the user.
*/   
  public ArrayList&lt;String&gt; getUserWords() {
  // You must fill this in.
     if (dictionary.contains(userWords))
     {
        userCount++;
        userList.add(userWords);
     }
     return userList;
  }

 /**
* Return a list of valid words identified by the machine.
*/   
  public ArrayList&lt;String&gt; getMachineWords() {
   // You must fill this in.
     if (dictionary.contains(wordSoFar))
     {
        machineCount++;
        machineList.add(wordSoFar);
     }
     return machineList;
  }

 /**
* Return the score of a list of valid words.
*/   
  public int getScore(ArrayList&lt;String&gt; words) {
  // You must fill this in.
     return -1;
  }     

 /**
* Play an example game.
*/  
//check the FileNotFoundException parts.
  public static void main (String[] args) throws FileNotFoundException 
  {
     BoggleBoard board = new BoggleBoard(BoggleBoard.SAMPLE_BOARD);
     BoggleDictionary dictionary = new BoggleDictionary();
     Boggle boggle = new Boggle();
     boggle.play();
  } 
 }
</code></pre>

<p><strong>BoggleBoard.java</strong></p>

<pre><code>/**
* BoggleBoard.java. Models a Boggle board.
*
* @author     
*   @author   
*   @version  2012-11-06
*
*/

import java.util.*;

public class BoggleBoard 
{
// default board dimension
   public int N = 4;
// sample board   
   public static String[][] SAMPLE_BOARD = 
  {               
            {"E","E","C","A"},
            {"A","L","E","P"},
            {"H","N","B","O"},
            {"Q","T","T","Y"}
            };

  public static String[][] board;   // grid of letters
  private String randomBoard[][] = new String[N][N];
  private LetterDie[] dice;   // letter dice used on board
  private int d = 0;


/**
* Create a new 4x4 BoggleBoard with a random
* letter die arrangement. This should simulate
* the shuffling of the board that would occur in
* a physical game.
*/
  public BoggleBoard() 
  {
     dice = initStandardDice();
     while (d &lt; 16)
        for (int i = 0; i &lt; 4; i++)
        {
           for (int j = 0; j &lt; 4; j++)
           {
              randomBoard[i][j] = (dice[d].getLetter());
              d++;
           }
        }
     board = randomBoard;
  }


/**
* Create a new BoggleBoard with a specified
* letter die arrangement. If the grid is null
* or if the grid is not square, this method
* throws an IllegalArgumentException.
*/
  public BoggleBoard(String[][] grid) 
  {
     if (grid == null) throw new NullPointerException();
     if (grid.length != grid[0].length) throw new IllegalArgumentException();

     dice = initStandardDice();
     board = grid;
     N = grid.length;
  }


/**
* Return the (i,j) letter on the board. The top-left
* of the board is (0,0). If row or col has an illegal
* value, this method throws an IllegalArgumentException.
*/   
  public String getLetter (int row, int col) 
  {
  // You must fill this in.
     if (row &lt; 0 || row &gt; N - 1 ||col &lt; 0 || col &gt; N - 1)
     {
        throw new IllegalArgumentException();
     }

     return board[row][col];
  }


/**
* Return the board dimension
*/   
  public int size() 
  {
  // DO NOT MODIFY THIS METHOD
     return N;
  }


/**
* Return a String representation of the board.
*/  
  public String toString() 
  {
  // DO NOT MODIFY THIS METHOD
     StringBuilder s = new StringBuilder();
     s.append("* * * *\n");   
     for (int i = 0; i &lt; N; i++) {
        for (int j = 0; j &lt; N; j++) 
           s.append(board[i][j] + " ");
        s.append("\n");
     }
     s.append("* * * *");
     return s.toString();
  }


/**
* Initialize the 16 letter die for a standard Boggle game.
*/   
  private LetterDie[] initStandardDice() 
  {
  // Official Boggle dice, except for QU on die #2
  //
  // DO NOT MODIFY THIS METHOD
  //
     LetterDie[] dice = new LetterDie[16];

     dice[0]  = new LetterDie("F", "O", "R", "I", "X", "B");
     dice[1]  = new LetterDie("M", "O", "Q", "A", "B", "J"); // should have QU
     dice[2]  = new LetterDie("G", "U", "R", "I", "L", "W");
     dice[3]  = new LetterDie("S", "E", "T", "U", "P", "L");
     dice[4]  = new LetterDie("C", "M", "P", "D", "A", "E");
     dice[5]  = new LetterDie("A", "C", "I", "T", "A", "O");
     dice[6]  = new LetterDie("S", "L", "C", "R", "A", "E");
     dice[7]  = new LetterDie("R", "O", "M", "A", "S", "H");
     dice[8]  = new LetterDie("N", "O", "D", "E", "S", "W");
     dice[9]  = new LetterDie("H", "E", "F", "I", "Y", "E");
     dice[10] = new LetterDie("O", "N", "U", "D", "T", "K");
     dice[11] = new LetterDie("T", "E", "V", "I", "G", "N");
     dice[12] = new LetterDie("A", "N", "E", "D", "V", "Z");
     dice[13] = new LetterDie("P", "I", "N", "E", "S", "H");
     dice[14] = new LetterDie("A", "B", "I", "L", "Y", "T");
     dice[15] = new LetterDie("G", "K", "Y", "L", "E", "U");

     return dice;
  }
</code></pre>

<p>}</p>

<p><strong>BoggleDictionary.java</strong></p>

<pre><code>/**
 * BoggleDictionary.java. An adaptor class that provides the
 * dictionary/lexicon behavior necessary for a Boggle game.
 *
 * @author     
 *  @author   
 *  @version  2012-11-06
 *
 */

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

 public class BoggleDictionary implements Iterable&lt;String&gt; {

 // Filenames of default word lists
  public static final String CSW  = "CSW12.txt";
  public static final String OWL  = "OWL.txt";
  public static final String UNIX = "words.txt";
  private TreeSet&lt;String&gt; tree = new TreeSet&lt;String&gt;();
  public File fileName = new File(UNIX);
  public Scanner scan = new Scanner(fileName); 
  private TreeSet&lt;String&gt; dictionary = new TreeSet&lt;String&gt;();
  Iterator&lt;String&gt; itr;

 // You must choose an appropriate type for the dictionary field.
 // You can't leave this field typed as 'Object.'

  private TreeSet&lt;String&gt; addToTree(File file) throws FileNotFoundException
  { 
     //fileName = new File("words.txt");
     //File fileName = new File(UNIX);
     //Scanner scan = new Scanner(fileName);

     while (scan.hasNextLine())
     {
        String word = scan.nextLine();
        tree.add(word);
     }
     return tree;
  }


/**
* Create a dictionary with a default word list.
*/
  public BoggleDictionary() throws FileNotFoundException
  {
     addToTree(fileName);
  // Change to construct the dictionary as appropriate, 
  // using one of the default word lists.
     dictionary = tree;
  }


/**
* Create a dictionary with the specified word list.
*/
  public BoggleDictionary(String wordlist)throws FileNotFoundException
  {
     addToTree(fileName);
  // Change to construct the dictionary as appropriate, 
  // using the specified word list.
     dictionary = tree;
  }

/**
* Is the string a word in the dictionary?
*/   
  public boolean contains(String str) 
  {
  // You must fill this in as appropriate and change the return value.
     return dictionary.contains(str);
  }


/**
* Is the string a prefix of some word in the dictionary?
*/   
  public boolean containsAsPrefix(String str) {
  // You must fill this in as appropriate and change the return value.
     return containsAsPrefix(str);
  }


/**
* Create an iterator over all the words in the dictionary.
* No specific word order is guaranteed.
*/   
  public Iterator&lt;String&gt; iterator() {
     Iterator&lt;String&gt; itr = dictionary.iterator();
     return itr;
  }

}
</code></pre>

<p><strong>LetterDie.java</strong></p>

<pre><code> /**
  * LetterDie.java. Models a single six-sided letter die
  * used in a Boggle game.
  *
  *  @author     
  * @author   
  * @version  2012-11-06
  *
  */

// DO NOT MODIFY THIS CLASS

  import java.util.Random;

  public class LetterDie {

  private String[] sides;             // the six sides of the die
  private int currentSideUp;          // which side is up?
  private Random rng = new Random();  // use to simulate die toss

/**
* Create a new die and randomly pick the side that's up.
*/
  public LetterDie(String side1, String side2, String side3,
           String side4, String side5, String side6) {
     sides = new String[] {side1,side2,side3,side4,side5,side6};
     toss();
  }


/**
* Return the letter that's showing.
*/
  public String getLetter() {
     return sides[currentSideUp];
  }


/**
* Toss the die to make a random letter show.
*/
  public void toss() {
     currentSideUp = rng.nextInt(6);
  }
}
</code></pre>

<p><strong>Test.java</strong></p>

<pre><code>   import java.io.*;
   import java.util.*;
   public class Test {
  private int N;                    // dimension of board
  private String[][] board;           // the board (a-z)
  private boolean[][] visited;      // for dfs
  private TreeSet&lt;String&gt; st;              // list of words

// create random N-by-N board
  public Test(TreeSet&lt;String&gt; st) {

     this.st = st;
     visited = new boolean[4][4];
     board = new String[4][4];
     board[0][0] = "H";
     board[0][1] = "A";
     board[0][2] = "I";
     board[0][3] = "L";
     board[1][0] = "F";
     board[1][1] = "O";
     board[1][2] = "M";
     board[1][3] = "T";
     board[2][0] = "S";
     board[2][1] = "K";
     board[2][2] = "L";
     board[2][3] = "P";
     board[3][0] = "F";
     board[3][1] = "J";
     board[3][2] = "U";
     board[3][3] = "D";
  }

// show all words, starting from each possible starting place
  public void showWords() {
     for (int i = 0; i &lt; 4; i++)
        for (int j = 0; j &lt; 4; j++)
           dfs("", i, j);
  }

// run depth first search starting at cell (i, j)
  private void dfs(String prefix, int i, int j) {
     if (i &lt; 0 || j &lt; 0 || i &gt;= 4 || j &gt;= 4) 
        return;

    // can't visited a cell more than once
     if (visited[i][j]) 
        return;

    // key to efficiency of backtracking algorithm
     //if (!st.containsPrefix(prefix)) 
        //return;

     // not allowed to reuse a letter
     visited[i][j] = true;

    // found a word
     prefix = prefix + board[i][j];
     if (st.contains(prefix)) 
        System.out.println(prefix);

    // consider all neighbors
     for (int ii = -1; ii &lt;= 1; ii++)
        for (int jj = -1; jj &lt;= 1; jj++)
           dfs(prefix, i + ii, j + jj);

     visited[i][j] = false;
  }

// just the board
  public String toString() {
     StringBuilder s = new StringBuilder();
     s.append("* * * *\n");   
     for (int i = 0; i &lt; 4; i++) {
        for (int j = 0; j &lt; 4; j++) 
           s.append(board[i][j] + " ");
        s.append("\n");
     }
     s.append("* * * *");

     return s.toString();
  }



  public static void main(String[] args) {

    // read in the list of words
     TreeSet&lt;String&gt; st = new TreeSet&lt;String&gt;();
     st.add("HAIL");
     st.add("LOAM");
     st.add("FOIL");
     st.add("SOIL");
     st.add("AIM");
     st.add("CHOCOLATE");

     Test boggle = new Test(st);
     System.out.println(boggle);
     boggle.showWords();
  }
}
</code></pre>

<p>I've got the same DFS implementation word for word in both test and boggle. In Test it works perfectly fine, gets all the words but the obvious one (chocolate) but in Boggle it goes through the DFS but still prints out just points in the array. Once again, just looking for a step in the right direction. Thanks!</p>
