Lab 4: Boggle Word Finder¹

• Assigned: Monday, January 31
• Check-in Post: Before 9pm Wednesday, February 2 (check-in forum)
• Due: 9pm Friday, February 5
• Collaboration: Individual assignment
• Handout: starter project
• Submit: Upload BoggleSolver.java to Lab 4.
• Reference:
  • Searching

Overview

In this lab you will implement a method to find words on a Boggle game board. 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:

• A valid word must be composed by following a sequence of adjacent dice—two dice are adjacent if they are horizontal, vertical, or diagonal neighbors.
• A valid word can use each die at most once.
• A valid word must contain at least 3 letters.
• A valid word must be in the dictionary (which typically does not contain proper nouns).

Here are some examples of valid and invalid words:

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

The goals for this lab are

• Practice implementing a recursive backtracking algorithm
• Practice elements of recursion including base case, recursive case, and a recursive helper method
• Play some Boggle :)

Preparatory Exercises

1. Read the rest of this writeup. Plan out on paper the basic pieces of your recursive backtracking algorithm:
   • What parameters will your recursive helper method take?
   • What will its base case be?
   • What will its recursive case be?
   • How will the helper method be called from getAllValidWords?
   • How will you know when to add something to the list of words?
   • What choice will you make (and undo) in the recursive case?
   • How will you use the methods of the BoggleBoard object? (It is likely you will need to use all of those listed Discussion)
2. Download the starter project, unzip it into its own folder, and open that folder in VS Code. In addition to the usual configuration files and the .java files for the lab, the starter project contains a number of text files (.txt) for Boggle boards and dictionaries. You shouldn’t need to do anything with these (some are used by the tests).
3. Run BoggleGame.java to make sure the provided components of the game work. You should see a Boggle board, a timer, and a place to enter words. You won’t be able to enter any words yet because your task is to implement the method that finds the legal words.

Discussion

All the components of the Boggle game except the method to find valid words are provided to you. Your task is to implement the

public Set<String> getAllValidWords(BoggleBoard board)

method in BoggleSolver.java. To know which sequences of letters are valid words, you need a dictionary. This is set up by the provided BoggleSolver constructor. Specifically, the class has a field dictionary that is a Set of the words in the dictionary.

A Set is a Java interface for a collection that contains no duplicate elements. For your purposes in this lab, you only need to use two of its methods:

• add(String s): adds s to the set, doing nothing if the string is already in the set
• contains(String s): returns true if s is present in the set

The getAllValidWords method you’re implementing returns a Set of strings containing all the words that can be made using board following the rules given in Overview. The starter code creates a HashSet object for you add words to and return. A HashSet implements the Set interface using the hashing technique we’re learning about this week.

BoggleBoard

You are provided with BoggleBoard.java for representing Boggle boards. Importantly for your purposes, it provides methods for getting the size of the board and the letter at each location and for keeping track of what locations have been used as part of a word. Here is the relevant API:

    /**
     * Returns the number of rows.
     * @return number of rows
     */
    public int rows()

    /**
     * Returns the number of columns.
     * @return number of columns
     */
    public int cols()

    /**
     * Returns the letter in row i and column j.
     * @param i the row
     * @param j the column
     * @return a String version of the letter in row i and column j,
     *         returning "Qu" when the letter is 'Q'
     */
    public String getLetter(int i, int j)

    /**
     * Marks the location at row i and column j as visited.
     * @param i the row
     * @param j the column
     */
    public void visit(int i, int j)

    /**
     * Marks the location at row i and column j as not visited.
     * @param i the row
     * @param j the column
     */
    public void unvisit(int i, int j)

    /**
     * Checks if the location at row i and column j is visited.
     * @param i the row
     * @param j the column
     * @return true if the location is marked as visited
     */
    public boolean isVisited(int i, int j)

    /**
     * Checks if all locations are visited.
     * @return true if all locations are marked as visited
     */
    public boolean allVisited()

    /**
     * Checks if the location at row i and column j is a valid board location.
     * @param i the row
     * @param j the column
     * @return true is the location is a valid board location
     */
    public boolean isValidLocation(int i, int j)

Procedure

You are free to implement finding valid words in any recursive way you see fit. That said, I strongly recommend using a recursive backtracking approach. I outline one possible such approach below.

Searching for a word on a Boggle board follows this basic process:

1. Select a location to start with
2. Try tracing out paths through adjacent locations, never using a location more than once
3. If the letters you’ve encountered form a word in the dictionary, add it to the list of words

To perform this search there are a some of things you need to keep track of:

• The board location you are currently on
• The letters you’ve encountered so far
• The locations you’ve already used

Since getAllValidWords only takes a board as a parameter, it won’t be able to recursively keep track of all of these. So you might implement a recursive helper method that does:

private void getAllValidWordsHelper(BoggleBoard board, Set<String> words, 
                                    String wordSoFar, int row, int col)

• row and col are the current board location.
• wordSoFar is a string of the letters you’ve encountered.
• words is the set of words created in getAllValidWords (our helper method needs to add words to it, so we pass it as a parameter).
• Conveniently, board itself can keep track of where you’ve visited using the visit(int i, int j), isVisited(int i, int j), and unvisit(int i, int j) methods.

This helper method will search for words starting at location (row, col), adding on letters it encounters to wordSoFar. Each recursive call is exploring the possible choices of next location to visit. To find all the words on a board, you need to start a search from each board location. This you can handle in getAllValidWords: loop over all board locations (use board.rows() and board.cols() to get the size of the board) and call getAllValidWordsHelper to start a search at each one.

How will you know if a word is in the dictionary? Use the contains method of the dictionary field: dictionary.contains(wordSoFar).

How will you “trace out paths through adjacent locations”? If you are at location (1, 1) of a 4-by-4 board, there are eight possible adjacent locations:

Note that the coordinates of the adjacent locations involve adding or subtracing 1 from the current row and/or column. Thus, we can nicely express these using nested for loops from row - 1 to row + 1 and from col - 1 to col + 1 where (row, col) is the current location. Of course, this will sometimes result in locations that are off the sides of the board. You can use board.isValidLocation to skip these.

An important part of recursive backtracking is stopping the search when you reach a dead end. In Boggle, a search has reached a dead end if the letters you’ve encountered so far (wordSoFar) don’t lead to any word in the dictionary. For example, if wordSoFar is "TX", there’s no point to exploring further because no word in the dictionary begins with "TX". One term for letters at the start of a word is prefix. BoggleSolver has a Set<String> field prefixes that contains all the prefixes to every word in the dictionary. For example, if the dictionary contains the word "DATA", prefixes will contain "D", "DA", and "DAT". You should only make a recursive call if prefixes.contains(wordSoFar).

Like other examples of recursive backtracking we’ve seen, the code you need to write doesn’t take very many lines (likely no more than 15 or 20 in any one method). That doesn’t mean it’s easy or obvious, however. Planning out ahead of time (step 1 of Preparatory Exercises) will be very helpful.

Testing

Of the 11 JUnit tests provided with the starter project, only 2 (findsSomeWordsTest and findsAllWordsTest) are part of your grade (see Grading). The others are intended to help you debug if the graded ones are failing. I have tried to give these tests useful error messages when they fail.

There is one testing situation to be aware of. If you do not use prefixes to avoid searching dead ends, as described in Procedure, your code will make an enormous amount of recursive calls. All the tests have a 2 second time limit, which should prevent running the tests from freezing VS Code in most cases. I have observed, however, that if I run all the tests at once with a print statement in my recursive method that doesn’t stop at dead ends, it causes VS Code to freeze. If you are debugging with print statements, take care to run just one test at a time.

Style

You are expected to submit a BoggleSolver.java that contains no checkstyle errors. It is ok to have checkstyle warnings in your submitted code, though I encourage you to fix them if you have time. Avoiding these warnings will become part of your grade on future labs.

You should ignore all Java warnings in BoggleBoard.java and BoggleGame.java.

Grading

This lab will be graded out of 30 points as shown below. While most of the points for this lab are associated with specific test cases, partial credit can be earned for test cases that don’t pass. It it possible to earn a passing graded even if your submission does not pass any tests. Partial credit will be awarded based on evidence of a good-faith effort to implement the related features. Comments explaining your approach can help earn partial credit.