Programming Assignment 4: Boggle

Write a program to play the word game Boggle®.

The Boggle game. Boggle is a word game designed by Allan Turoff and distributed by Hasbro. It involves a board made up of 16 cubic dice, where each die has a letter printed on each of its 6 sides. At the beginning of the game, the 16 dice are shaken and randomly distributed into a 4-by-4 tray, with only the top sides of the dice visible. The players compete to accumulate points by building valid words from the dice, according to these rules:

Here are some examples of valid and invalid words:

pins     pines     dates
PINS
(valid)
    PINES
(valid)
    DATES
(invalid—dice not adjacent)
 
pint     tepee     sid
PINT
(invalid—path not sequential)
    TEPEE
(invalid—die used more than once)
    SID
(invalid—word not in dictionary)


Scoring. Words are scored according to their length, using this table:

  word length     points  
0–2 0
3–4 1
5 2
6 3
7 5
  8+ 11

The Qu special case. In the English language, the letter Q is almost always followed by the letter U. Consequently, the side of one die is printed with the two-letter sequence Qu instead of Q (and this two-letter sequence must be used together when forming words). When scoring, Qu counts as two letters; for example, the word QuEUE scores as a 5-letter word even though it is formed by following a sequence of only 4 dice.

Qu


Your task. Your challenge is to write a Boggle solver that finds all valid words in a given Boggle board, using a given dictionary. Implement an immutable data type BoggleSolver with the following API:

public class BoggleSolver { // Initializes the data structure using the given array of strings as the dictionary. // (You can assume each word in the dictionary contains only the uppercase letters A through Z.) public BoggleSolver(String[] dictionary) // Returns the set of all valid words in the given Boggle board, as an Iterable. public Iterable<String> getAllValidWords(BoggleBoard board) // Returns the score of the given word if it is in the dictionary, zero otherwise. // (You can assume the word contains only the uppercase letters A through Z.) public int scoreOf(String word) }
It is up to you how you search for and store the words contained in the board, as well as the dictionary used to check them. If you need help getting started, some hints are available on the checklist.


The board data type. We provide an immutable data type BoggleBoard.java for representing Boggle boards. It includes constructors for creating Boggle boards from either the 16 Hasbro dice, the distribution of letters in the English language, a file, or a character array; methods for accessing the individual letters; and a method to print out the board for debugging. Here is the full API:

public class BoggleBoard { // Initializes a random 4-by-4 Boggle board. // (by rolling the Hasbro dice) public BoggleBoard() // Initializes a random m-by-n Boggle board. // (using the frequency of letters in the English language) public BoggleBoard(int m, int n) // Initializes a Boggle board from the specified filename. public BoggleBoard(String filename) // Initializes a Boggle board from the 2d char array. // (with 'Q' representing the two-letter sequence "Qu") public BoggleBoard(char[][] a) // Returns the number of rows. public int rows() // Returns the number of columns. public int cols() // Returns the letter in row i and column j. // (with 'Q' representing the two-letter sequence "Qu") public char getLetter(int i, int j) // Returns a string representation of the board. public String toString() }

Testing. We provide a number of dictionary and board files for testing.

The following test client takes the filename of a dictionary and the filename of a Boggle board as command-line arguments and prints out all valid words for the given board using the given dictionary.
public static void main(String[] args) { In in = new In(args[0]); String[] dictionary = in.readAllStrings(); BoggleSolver solver = new BoggleSolver(dictionary); BoggleBoard board = new BoggleBoard(args[1]); int score = 0; for (String word : solver.getAllValidWords(board)) { StdOut.println(word); score += solver.scoreOf(word); } StdOut.println("Score = " + score); }
Here are two sample executions:
% java-algs4 BoggleSolver dictionary-algs4.txt board4x4.txt % java-algs4 BoggleSolver dictionary-algs4.txt board-q.txt AID EQUATION DIE EQUATIONS END ... ENDS QUERIES ... QUESTION YOU QUESTIONS Score = 33 ... TRIES Score = 84

Performance. If you choose your data structures and algorithms judiciously, your program can preprocess the dictionary and find all valid words in a random Hasbro board (or even a random 10-by-10 board) in a fraction of a second. To stress test the performance of your implementation, create one BoggleSolver object (from a given dictionary); then, repeatedly generate and solve random Hasbro boards. How many random Hasbro boards can you solve per second? For full credit, your program must be able to solve thousands of random Hasbro boards per second. The goal on this assignment is raw speed—for example, it's fine to use 10× more memory if the program is 10× faster.

Interactive game (optional, but fun and no extra work). Once you have a working version of BoggleSolver.java, download, compile, and run BoggleGame.java to play Boggle against a computer opponent. To enter a word, either type it in the text box or click the corresponding sequence of dice on the board. The computer opponent has various levels of difficulty, ranging from finding only words from popular nursery rhymes (easy) to words that appear in Algorithms 4/e (medium) to finding every valid word (humbling).

Boggle GUI

Challenge for the bored. Here are some challenges:

Unless otherwise stated, use the dictionary-yawl.txt dictionary. If you discover interesting boards, you are encouraged to share and describe them in the Discussion Forums.

Deliverables. Submit BoggleSolver.java and any other supporting files (excluding BoggleBoard.java and algs4.jar). You may not call any library functions other those in java.lang, java.util, and algs4.jar.

This assignment was developed by Matthew Drabick and Kevin Wayne, inspired by Todd Feldman and Julie Zelenski's classic Nifty Boggle assignment from Stanford.
Copyright © 2013.