# Boggle Solver (Recursive Portion)by Isai Damier, Android Engineer @ Google

```/***********************************************************************
* 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);
}
}
}
}```