Boggle Solver
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/***********************************************************************
 * 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
}