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