Boggle Solver
/*********************************************************************** * 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 List<String> dictionary, char[][] board * @return Set<String> * * Description: This function takes in a boggle board and a * dictionary; then efficiently finds all sequences of * characters on the boggle board that form valid words. * * Technical Details: * * 0] Load all the words into a trie * 1] Create an empty set to store all the valid words found * NOTE: Since each letter on the board may potentially be the start * of a number of words, then it is necessary to loop through the * board to use each letter as the start of a sequence. * 2] For each letter on the board: * a -- create a bit table the size of the boggle board to track * that a lettered tile is not used more than once within a * word: false means not yet used; true means used. * b -- call the recursive function 'solver', which will find all * possible words starting with said letter. The parameters * to the recursive solver are: the boggle board; the bit * table, which tracked used letters for the forming sequence; * the dictionary; the character sequence to use as word or * prefix (at the beginning the sequence is just one letter); * the x- and y-coordinate of the last character added, * which is needed to know which other letters are adjacent * to said character; and the result set, where the recursive * solver stores each word found. * 3] return the resulting set of valid words. ****************************************************************/ public Set<String> solver(List<String> dictionary, char[][] board) { Trie lexicon = new Trie(); for (String word : dictionary) { lexicon.addWord(word); } Set<String> result = new HashSet<String>(); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { boolean tracker[][] = new boolean[board.length][board[0].length]; solver(board, tracker, lexicon, board[i][j] + "", i, j, result); } } return result; }//solver }
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); } } } }