Boggle Solver (Recursive Portion)
by Isai Damier

/***********************************************************************
 * Author: Isai Damier
 * Title: BoggleSolver.java
 * Project: geekviewpoint
 * Package: game.programming
 *
 * Description:
 *   Boggle is a word game. A player is given a rectangular board of
 *   letters and is expected to find words by chaining together
 *   adjacent letters. A chain of letters may form a straight line
 *   (horizontal, vertical, or diagonal), or a spiral, or any other
 *   random pattern. Boggle has one rule: the same lettered tile may
 *   not be used more than once.
 *
 *   Now when a real human person plays boggle, the person
 *   implicitly uses the dictionary in his/her head, as it were.
 *   For a program to play boggle, however, it must be given a
 *   dictionary so to know which words are valid.
 *
 *   The best data-structure to hold a dictionary for a boggle
 *   solver is a trie (http://www.geekviewpoint.com/java/trie/add_word).
 *   As a prefix tree, a trie allows the solver to check if a sequence
 *   of letter is a prefix. If a sequence is not a prefix, the solver can
 *   simply stop elongating the sequence and try a different sequence.
 *   Hence the solver will complete the solution much much faster.
 *
 *   Disclaimer: Boggle is a word/board game designed by Allan Turoff
 *   and trademarked by Parker Brothers, a division of Hasbro.
 *   GeekViewpoint is not affiliated with Allan Turoff or Hasbro.
 ***********************************************************************/ 
 package game.programming;

import datastructure.Trie;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class BoggleSolver {

  /*********************************************************************
   * Function: solver
   * @param
   *     char[][] board: the boggle board, each entry represents
   *       a lettered tile.
   *     boolean[][] tracker: a bit table used to track whether a
   *       letter has already been used.
   *     Trie lexicon: the dictionary to validate words.
   *     String word: the word to look up. If the word is valid, then
   *       add it to the result set; if it's a prefix, use it to
   *       form other words.
   *     int x: horizontal coordinate of the letter being considered.
   *     int y: vertical coordinate of the letter to being considered.
   *     Set<String> result: the list of valid words.
   * @return
   *
   * Description: This function recursively forms words by adding one
   *   letter at a time to a given prefix/word.
   *
   *   0] If the given word/prefix is a valid dictionary word,
   *      add it to the result set.
   *   1] If the given word/prefix is not a valid prefix,
   *      then return: abort elongating that sequence.
   *   3] Make a deep copy of the tracker and call it tmp.
   *   4] In tmp, the child tracker, set the coordinate of
   *      the present letter to true, to mark it as been used.
   *   2] For each letter L adjacent to the letter at x,y:
   *      recursively call solver (this function) on word+L.
   *      For example if word="rat" and L="s" then word+L="rats".
   *      A letter is adjacent to x,y if it is located at any of
   *      the following locations: (x-1,y-1); (x,y-1); (x+1,y-1);
   *      (x+1,y); (x+1,y+1); (x,y+1); (x-1,y+1); (x-1,y).
   ********************************************************************/
  private void solver(
          char[][] board,
          boolean[][] tracker,
          Trie lexicon,
          String word,
          int x, int y,
          Set<String> result)
  {

    if (lexicon.isWord(word)) { result.add(word); }

    if (!lexicon.isPrefix(word)) { return; }

    boolean[][] tmp = deepCopy(tracker);
    tmp[x][y] = true;

    //upper left
    if (0 <= x - 1 && 0 <= y - 1 && !tmp[x - 1][y - 1]){
      solver(board,tmp,lexicon, word+board[x-1][y-1], x-1, y-1, result);
    }

    //up
    if (0 <= y - 1 && !tmp[x][y - 1]){
      solver(board, tmp, lexicon, word + board[x][y-1], x, y-1, result);
    }

    //upper right
    if (x + 1 < board.length && 0 <= y - 1 && !tmp[x + 1][y - 1]){
      solver(board,tmp,lexicon, word+board[x+1][y-1], x+1, y-1, result);
    }

    //right
    if (x + 1 < board.length && !tmp[x + 1][y]){
      solver(board, tmp, lexicon, word + board[x+1][y], x+1, y, result);
    }

    //lower right
    if (x+1 < board.length && y+1 < board[0].length && !tmp[x+1][y+1]){
      solver(board,tmp,lexicon, word+board[x+1][y+1], x+1, y+1, result);
    }

    //down
    if (y + 1 < board[0].length && !tmp[x][y + 1]){
      solver(board, tmp, lexicon, word + board[x][y+1], x, y+1, result);
    }

    //lower left
    if (0 <= x - 1 && y + 1 < board[0].length && !tmp[x - 1][y + 1]){
      solver(board,tmp,lexicon, word+board[x-1][y+1], x-1, y+1, result);
    }

    //left
    if (0 <= x - 1 && !tmp[x - 1][y]){
      solver(board, tmp, lexicon, word + board[x-1][y], x-1, y, result);
    }
  }
}
package game.programming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import org.junit.After;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;

public class BoggleSolverTest {

  List<String> goodWords, badWords, dictionary;
  BoggleSolver boggleSolver = new BoggleSolver();

  /**
   * @throws Exception
   *
   * Description: create the dictionaries.
   */
  @Before
  public void setUp() throws Exception {
    goodWords = Arrays.asList("readied", "reaved", "randie", "navaid",
            "larned", "errand", "envied", "endive", "earned", "darnel",
            "darned", "dandle", "daidle", "adread", "vexed", "veena",
            "varna", "varan", "vaned", "reran", "reave", "raved",
            "ranee", "narre", "naled", "lande", "evade", "erned",
            "eland", "eaved", "eaned", "drear", "dread", "drave",
            "dived", "divan", "denar", "darre", "darer", "arear",
            "aread", "alane", "aland", "adrad", "vied", "vide", "vare",
            "vara", "vane", "vade", "rear", "rean", "read", "rave",
            "rare", "rand", "rana", "rale", "rade", "need", "nave",
            "nare", "nard", "nala", "nada", "lend", "leed", "larn",
            "lare", "lane", "land", "lana", "idle", "idee", "exed",
            "erne", "elan", "eide", "eevn", "eave", "earn", "eard",
            "drad", "dive", "diva", "died", "deva", "deid", "deev",
            "deen", "darn", "dare", "dada", "avid", "arna", "area",
            "arar", "anal", "alee", "alar", "alan", "aide", "vie",
            "vid", "via", "vex", "vee", "var", "van", "vae", "ran",
            "rad", "nee", "ned", "nae", "lex", "lee", "led", "lar",
            "ide", "err", "ern", "era", "end", "eld", "een", "eel",
            "ear", "ean", "div", "die", "did", "dex", "dev", "den",
            "del", "dei", "dee", "dan", "dae", "dad", "ave", "ava",
            "are", "ard", "ane", "and", "ana", "ale", "ala", "aid",
            "ade", "aal");

    badWords = Arrays.
            asList("amazon", "forest", "dangerous", "lovely", "resistible");

    dictionary = new ArrayList<String>();
    dictionary.addAll(goodWords);
    dictionary.addAll(badWords);
  }

  /**
   * @throws Exception
   *
   * Description: Destroy all resources after use.
   */
  @After
  public void tearDown() throws Exception {
    goodWords = badWords = null;
    boggleSolver = null;
  }

  /**
   * Test of solver method, of class BoggleSolver.
   */
  @Test
  public void testSolver() {
    System.out.println("solver");
    char[][] board = {{'a', 'l', 'e', 'x'},
                      {'a', 'n', 'd', 'e'},
                      {'r', 'a', 'v', 'i'},
                      {'e', 'r', 'd', 'a'}
    };

    Set<String> result = boggleSolver.solver(goodWords, board);
    assertEquals(result.size(), goodWords.size());
    for (String g : goodWords) {
      if (!result.contains(g)) {
        fail("Boggle solver fails to find " + g);
      }
    }
    for (String b : badWords) {
      if (result.contains(b)) {
        fail("Boggle solver should not have found " + b);
      }
    }
  }
}