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: finding all the words on the board and achieving 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 by tracing a path through adjoining letter cubes, using each cube at most once in the word.

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

img of boggle board

The game board will be represented as a Grid<char>. Each location in the grid is a letter cube, and the character at that grid location is the letter on the top face of the cube.

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

  • The word must be at least 4 letters long.
  • The word must be contained in a list of valid English words.
    • We provide a Lexicon of English words that you can use to check this constraint.
  • The word can be formed by tracing a path through adjoining letter cubes, using any given cube at most once.
    • On the Boggle board, a cube is adjoining to its neighbors in the four cardinal directions and along the four diagonals. A cube has between 3 and 8 neighbors, depending on its location on the board.
  • The word has not already been scored.
    • Each word is scored only once, even if you can form same word following two different paths through the letter cubes.

Points are scored for a word according to its length. A word with 3 or fewer characters is invalid by the above 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.

To get familiar with the rules of the game and how the algorithm that you're developing fits into the grand scheme of things, try the computer player of our online Boggle game to see the power of this application of recursive backtracking.

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 recursive 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 tracing 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

  • Use of ADTs. The Grid/GridLocation and Lexicon youā€™ve previously used will come in handy. You may also use other ADTs from the Stanford library. Take care to select data structures whose operations efficiently support the needs of the task. As it can be expensive to make copies of large data structures, pass these variables by reference to allow efficient sharing without copying.
  • English lexicon. Our EnglishWords.txt 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 functions. Our starter code includes prototypes and test cases for some recommended helper functions. You may also use additional helper functions of your own design with whatever parameters you like. The only firm requirement about specific prototypes 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 fail to apply 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 the expected score, 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, fill the remaining locations with some non-letter character such as *. A 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 stress test on a fully populated board, configure the board in the online Boggle game to match your test case and compare your result to the score of words found by the computer player.

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 have a tool that lets you win any Boggle game against your friends and family. (We only ask that you cut us for a small fraction of your winnings šŸ˜‰)

Extension

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.