Boggle Solver

Boggle is a game where the aim is to find words from within grids of letters.  In a standard game of Boggle the letters are arranged in a 4×4 grid and words can be formed by joining adjacent letters (this includes horizontally, vertically & diagonally) but each grid element can only be visited once per word.

The aim of the game is to find as many words of 3 letters or more as possible within a time limit and points are awarded based on the length & number of words that have been found.

For more information see Boggle

Solving the Problem

This problem can be divided into several smaller elements:

• A Dictionary that contains all of the acceptable words
• A Grid which allows the generation of random arrangement of letters.  This can be extended to use a simulation of the dice that are used in the physical game of Boggle so that an appropriate frequency of vowels & consonants are presented.
• An algorithm that traverses the grid to find the words that are contained within it’s arrangement of letters.

Dictionary.java

Let’s start with the Dictionary.  Rather than attempt to emulate Samuel Johnson and build the dictionary from scratch, we will start with a text file which contains all of the allowed words.  Each word will be read from the file and stored it as an element in a Collection, I opted to use a NavigableSet as all the elements are sorted and it provides a very elegant way to retrieve subsets of the collection which will come in very useful. We will be using this NavigableSet as if it was a Trie.

Read a file into a NavigableSet

public Dictionary(final File dictionaryFile) throws IOException {
	InputSupplier supplier = Files.newInputStreamSupplier(dictionaryFile);
	words = CharStreams.readLines(
			CharStreams.newReaderSupplier(supplier,
					Charset.defaultCharset()),
			new LineProcessor() {
				final NavigableSet lines = new TreeSet();
				public NavigableSet getResult() {
					return lines;
				}

				public boolean processLine(String line) throws IOException {
					lines.add(line.toLowerCase());
					return true;
				}
			});
}

Once the words have been loaded into the Dictionary it becomes very simple to add a couple of methods, one to see if a specific sequence is an exact match for a word in the dictionary
and another to return the collection of words which start with a supplied prefix:

Check for Words in the Dictionary

/**
 * Check if a specific sequence of letters appears in the dictionary.
 *
 * @param possibleWord The string whose existence in the Dictionary is being queried.
 * @return true if this is a known word, otherwise false.
 */
public boolean containsWord(final String possibleWord) {
	return words.contains(possibleWord.toLowerCase());
}

/**
 * Find all of the words in the Dictionary which start with a given sequence of letters.
 *
 * @param prefix
 * @return A Dictionary which contains only those known words which start with the supplied prefix.
 */
public Dictionary getChildWords(String prefix) {
	prefix = prefix.toLowerCase();
	return new Dictionary(words.subSet(prefix, false, prefix + "zzzz", true));
}

Grid.java

The Grid itself is very straightforward, it just contains a 2D array of the characters and is initialised by passing a single String which contains all of the visible letters in the grid. The only slight quirk is that in Boggle the letter ‘q’ is treated as if it is the combination of ‘qu’ and this wrinkle is applied when the grid is populated.

Populate the Grid

public class Grid {
	...

	public static final int GRID_SIZE = 4;
	final String[][] grid = new String[GRID_SIZE][GRID_SIZE];

	public Grid(String letters)
	{
		if ( StringUtils.length(letters) != GRID_SIZE * GRID_SIZE ){
			throw new IllegalArgumentException("");
		}
		letters = letters.toLowerCase();
		for (int i = 0; i < GRID_SIZE; i++ )
		{
			for ( int j = 0; j < GRID_SIZE; j++)
			{
				char character = letters.charAt((i * GRID_SIZE ) + j );
				grid[i][j] = "" + ( character == 'q' ? "qu" : character );
			}
		}
	}
	...
}

DiceSet.java

All that was left to do was to create a method to generate a random sequence of letters. To do this I created a basic Dice class with a letter on each side and a roll() method which returned a random side from the dice. I initialised a collection of these Dice instances with each dice holding a specific set of letters as per the standard Boggle game (new variant in this case):

Generate Random Letters for Grid

public final class BoggleDiceSet implements LetterGenerator {

	private final List<Dice> dice = new ArrayList<Dice>();

	public BoggleDiceSet()
	{
		addDice("AAEEGN");
		addDice("ELRTTY");
		addDice("AOOTTW");
		addDice("ABBJOO");
		addDice("EHRTVW");
		addDice("CIMOTU");
		addDice("DISTTY");
		addDice("EIOSST");
		addDice("DELRVY");
		addDice("ACHOPS");
		addDice("HIMNQU");
		addDice("EEINSU");
		addDice("EEGHNW");
		addDice("AFFKPS");
		addDice("HLNNRZ");
		addDice("DEILRX");
	}

	private void addDice(String sides) {
		List letters = new ArrayList(sides.length());
		for ( int i = 0; i < sides.length(); i++){
			letters.add(String.valueOf(sides.charAt(i)));
		}
		dice.add(new Dice(letters));
	}

	private List<Dice> shuffleDice(){
		Collections.shuffle(dice);
		return dice;
	}

	public String generateLetters(){
		StringBuilder sb = new StringBuilder();
		for (Dice die : shuffleDice()) {
			sb.append(die.roll());
		}
		return sb.toString();
	}

}

GridTraverser.java

In order to locate the words in the Grid we will need to iterate through each of the letters in the grid and then recursively visit each adjacent letter which has not already been visited in this sequence. As we go through this recursion we need append each character onto a character sequence and check if the sequence matches an exact word and then if there are any words in the dictionary which are prefixed by this character sequence. The recursion continues until there are no words in the dictionary which are prefixed by the character sequence.

public Set<String> findWords(Grid letterGrid, Dictionary dictionary)
{
	final Stack<GridPosition> visitedLetters = new Stack<GridPosition>();
	final Set<String> foundWords = new TreeSet<String>();

	for (int i = 0 ; i < LetterGrid.GRID_SIZE; i++ ){
		for ( int j = 0; j < LetterGrid.GRID_SIZE; j++ ){
			findWords(i, j, "", letterGrid, visitedLetters, dictionary, foundWords );
		}
	}
	return foundWords;
}

private void findWords(int i, int j, String prefix, LetterGrid letterGrid,
		Stack<GridPosition> visitedLetters, Dictionary dictionary,
		Set<String> foundWords) {
	visitedLetters.push(new GridPosition(i,j));
	String possibleWord = prefix + letterGrid.getLetterAt(i, j);
	if (dictionary.containsWord(possibleWord)) {
		addFoundWord(foundWords, possibleWord);
	}
	Dictionary childDictionary = dictionary.getChildWords(possibleWord);
	if (!childDictionary.isEmpty()) {
	for (int x = Math.max(0, i - 1); x < Math.min(i + 2,
				LetterGrid.GRID_SIZE); x++) {
			for (int y = Math.max(0, j - 1); y < Math.min(j + 2,
					LetterGrid.GRID_SIZE); y++) {
				if (!visitedLetters.contains(new GridPosition(x,y))) {
					findWords(x, y, possibleWord, letterGrid,
							visitedLetters, childDictionary,
							foundWords);
				}
			}
		}
	}
	visitedLetters.pop();
}