Assign4: Boggle Score

The Game of Boggle

The word game Boggle™ is a beloved part of the CS106B canon for its fun and engaging use of recursive search. While previous versions of CS106B have asked students to implement many parts of the game, we are scaling things down this quarter to focus on the interesting recursive problem at the core of the game – how do you find all the possible words on the board to achieve the highest possible score?

The Boggle game board is a square grid onto which you randomly distribute a set of letter cubes. You find a word on the board by tracing by a path through adjoining letter cubes, using each cube at most once in word.

The diagram below shows a sample board. Follow the arrows to trace the path for the word peace.

In this part of the assignment, we will use a Grid<char> to represent the game board. Each location in the grid represents a cube, where the character at that grid location represents the letter on the face of the cube.

A word is valid for a given board if it meets all of the following conditions:

• It is at least 4 letters long.
• It is contained in a list of valid English words.
  • We have provided an already-constructed Lexicon object that you can use to enforce this constraint.
• It can be formed by tracing a path through adjoining letter cubes, using any given cube at most once.
  • In particular, the definition of "adjoining" letter cubes here refers to all cubes that are potentially to the left, right, top, bottom, and the four diagonals of the current cube. A cube can have up to a maximum of 8 possible neighbors, if it is completely surrounded by other letter cubes.
• It has not already been formed by another path on the board
  • That is, multiple paths on the board can result in finding the same word, points for the word are counted only once.

Points are scored for a word according to its length. A word with 3 or fewer characters is invalid by the abover criteria and is thus worth zero points. A 4-letter word earns 1 point, a 5-letter word is 2 points; 6-letter words earn 3 points; and so on.

Your task

You are to write a function that computes the total score for all the words found on a given Boggle board. The function prototype is

int scoreBoard(Grid<char>& board, Lexicon& lex)

The function operates by recursively exploring the board to find all words and tallying up the points. When designing your recurisve approach to this problem, consider the following two important ideas:

• Backtracking. Searching the board to find words is an ideal application for recursive backtracking. The general idea is to do a search starting from each of the 16 letter cubes, recursively exploring all paths that start from a cube and trace through its neighbors.
• Marking. You don't want to visit the same letter cube twice during a given exploration, so your search needs some way to "mark" whether a letter cube has been visited or not. The choice of how you manage the marking is up to you; any efficient and effective choice is fine with us.

Notes

We highly recommend reading through the entirety of these notes before getting started on the problem.

• Use of ADTs. The Grid/GridLocation and Lexicon you’ve previously used will come in handy here and you may also use other ADTs from the Stanford library. Be sure to select data structures whose operations efficiently support the needs of the task. Also note it can be expensive to make copies of large data structures, so pass these large data structures by reference to allow efficient sharing without copying.
  • Minor convenience: Given a GridLocation loc, you can iterate over 3x3 neighbor locations like this:

      for (GridLocation nbr: loc.neighbors())
    

    This definition of neighbors was ill-suited for maze, but perfect for Boggle.

• English lexicon. Our EnglishWords Lexicon contains over 125,000 words, four times as many as the average person’s vocabulary. With this vast repertoire of obscure words and the power of exhaustive recursion, a Boggle computer player is very hard to beat!
• Helper/wrapper functions. Our starter code includes prototypes and test cases for some recommended helper functions. You may also use additional/different helper/wrapper functions of your design with whatever parameters you like. The only firm requirement is that the function scoreBoard is implemented to exactly match the prototype above.
• Efficiency. Scoring a board should be nearly instantaneous, less than a second. This will require efficient choices in ADTs (see above) and judicious pruning (see below).
• Pruning. An important efficiency consideration for any exhaustive recursion is pruning dead-end searches. The Lexicon containsPrefix function reports whether any words in the lexicon begin with a given prefix. If the first cube you examine is the letter Z and its neighbor is X, the initial path is ZX. A call to lex.containsPrefix("ZX") that returns false informs you that the lexicon contains no words that begin with this prefix. The search should give up on this path and move on to other more promising combinations. If you miss this optimization, you’ll find yourself taking long coffee breaks while the computer is futilely looking for words like zxgub, zxaep, etc. Even though you may love coffee, this is obviously not a great use of your time.
• Testing. The starter code contains some provided tests to get you started on testing. Here are some additional suggestions on how to take it from here:
  • The one result from scoreBoard is the score tally. When it doesn't match expected, the number alone offers little information to diagnose. To better support your testing efforts, you may want to gather the found words and compare to the expected words to identify discrepancies.
  • Identifying the words contained in a board is made simpler by deliberately constructing the board to have very few words. For example, after strategically placing a few targeted letters into the grid, use * (some non-letter) for the remaining locations. Any path containing non-letters AN* should be discarded by your prefix pruning and this will drastically thin out the number of paths/levels of recursion you have to trace through.
  • When ready for a bigger stress test on a fully populated board, try the computer player of our online Boggle game to find the words and score the board to use as a comparison.

Hooray for you! With your success on this task, you are now well on your way to become a master in the practice of recursion! And you also have a tool that lets you win any Boggle game against your friends and family as well…

Extensions

• Further board explorations. The standard Boggle game comes with sixteen letter cubes, each with particular letters on each of their six faces. The letters on each cube are not random; they were chosen in such a way that common letters come up more often and it is easier to get a good mix of vowels and consonants. Here are the letters on all six faces of the standard cubes:

  AAEEGN, ABBJOO, ACHOPS, AFFKPS, AOOTTW, CIMOTU, DEILRX, DELRVY, DISTTY, EEGHNW, EEINSU, EHRTVW, EIOSST, ELRTTY, HIMNQU, HLNNRZ

  To configure a random board from the standard cubes, shuffle the cubes into grid locations and randomly select the face-up letter for each cube. Some Boggle boards constructed from the standard cubes are a lot more fruitful that others. Exploring in code can tell you more about this. Is there an arrangement of the standard cubes that produces a board containing no words? What about an arrangement that produces a longest word, maybe even a word that uses all the cubes? What is the highest-scoring board you can construct? Recursion will be handy in trying out all the possible arrangements, but there are a lot of options (do the math on all the permutations . . .), so you may need to come up with some heuristics to direct your explorations.