Thanks to Julie Zelenski and Eric Roberts for creating this assignment, and to Chris Piech and Marty Stepp for modifications.
The classic CS106B assignment is based off a real life game called Boggle. Image courtesy of Rich Brooks (Flickr)
It's time for a CS106 classic, the venerable word game Boggle! The Boggle game board is a square grid onto which you randomly distribute a set of letter cubes. The goal is to find words on the board by tracing a path through adjoining letters.
Your assignment is to write a program that plays a fun, graphical rendition of this little charmer, adapted for the human and computer to play pitted against one another. You’ll quickly learn you have little hope of defeating the computer, but it’s awesome to realize you wrote this program that can so soundly thrash you again and again!
This assignment will introduce you to classes, but the main focus is on designing and implementing recursive algorithms. The starter code for this project is available as a ZIP archive. A demo is available as a JAR.
Turn in only the following files via the Paperless submitter:
Boggle.h / Boggle.cpp
: files for a Boggle class representing the state of the current Boggle gameboggleplay.cpp
: client to perform console UI and work with your Boggle class to play a gameA previously-recorded YEAH hours session for Boggle has been posted on Canvas, under "Beta - Lecture Videos", in the YEAH Hours folder.
You may optionally work on this assignment as a pair programming assignment.
If you would like to work in a pair on this assignment, you may, under the following
conditions:
Boggle is a game played on a square grid onto which you randomly distribute a set of letter cubes. Letter cubes are 6-sided dice, except that they have a letter on each side rather than a number. The goal is to find words on the board by tracing a path through neighboring letters. Two letters are neighbors if they adjoin each other horizontally, vertically, or diagonally. There are up to eight letters neighboring a given cube, and each cube can be used at most once in a word. In the real-life version of this game, all players work at the same time, listing the words they find on a piece of paper. When time is called, duplicates are removed from the lists and the players receive one point for each unique word, that is, for each word that player found that no other player was able to find.
You will write a program that plays this game, adapted for one human to play against a computer opponent. Unfortunately, the computer knows recursive backtracking, so it can find every word on the board and destroy you every time. But it's still fun to write a program that can resoundingly beat you again and again.
To begin a game, you shake up the letter cubes and lay them out on the board. The human player plays first, entering words one by one. Your code first verifies that the word is valid, then you add it to the player's word list and award the player points according to the word's length (one point per letter ≥ 4). A word is valid if it meets all of the following conditions:
Here is an excerpted sample log of execution for a round of the game:
Do you want to generate a random board? y It's your turn! FYCL IOMG ORIL HJHU ... Your words (3): {"FOIL", "FORM", "ROOF"} Your score: 3 Type a word (or Enter to stop): room You found a new word! "ROOM" ... Your words (5): {"FOIL", "FORM", "ROOF", "ROOM", "ROOMY"} Your score: 6 Type a word (or Enter to stop): It's my turn! My words (16): {"COIF", "COIL", "COIR", "CORM", "FIRM", "GIRO", "GLIM" "HOOF", "IGLU", "LIMO", "LIMY", "MIRI", "MOIL", "MOOR", "RIMY", "ROIL"} My score: 16 Ha ha ha, I destroyed you. Better luck next time, puny human!
As the log shows, once the player has found as many words as they can, the computer takes a turn. The computer searches through the board to find all the remaining words and awards itself points for those words. The computer typically beats the player, since you will program it to find all possible words left.
Your program's output format should exactly match the abridged log of execution above. Here are more examples of game logs (the text comparison files are also in the output
folder of the starter project). You can compare your text output against the files below by selecting "compare output" from the "file" menu of the console program window. You can also use the Output Comparison tool on the website under the "Tools" tab.
The real 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. We want your Boggle game to match this. The following table shows the letters represented on each of the sixteen cubes from the original Boggle (i.e., all six faces for each of the cubes). Our starter code declares two different cube arrays, one with the 16 cubes and another for an optional 25-cube extension. The 16 cubes are shown below:
At the beginning of each game, "shake" the board cubes. There are two different random aspects to consider:
AAEEGN
cube should not always appear in the top-left square of the board; it should randomly appear in one of the 16 available squares with equal probability.)
AAEEGN
cube should not always show A
; it should randomly show A
1/3 of the time, E
1/3 of the time, G
1/6 of the time, and N
1/6 of the time.)
shuffle.h
with a shuffle function you can use to rearrange the elements of an array, Vector, or Grid. See shuffle.h if you are curious about how the shuffling algorithm works.
Your game must also have an option where the user can enter a manual board configuration. For this option, rather than randomly choosing the letters that will be on the board, the user enters a string of 16 characters, representing the cubes from left to right, top to bottom. (This is also a useful feature for testing your code.) Verify that the user's string is long enough to fill the board and re-prompt if it is not exactly 16 characters in length. Also re-prompt the user if any of the 16 characters is not a letter from A-Z. Your code should work case-insensitively. You do not need to check whether the 16 letters typed could actually be formed from the 16 letter cubes; just accept any 16 alphabetic letters.
The human player enters each word they finds on the board. As we described above, for each word the user types, you must check that it is at least four letters long, contained in the English dictionary, has not already been included in the player's word list, and can be formed on the board from neighboring cubes. If any condition fails, alert the user. There is no penalty for trying an invalid word, but neither do invalid words count toward the player's list or score.
If the word is valid, you add the word to the player's word list and score. The length of the word determines the score, with each letter ≥ 4 being worth 1 point. For example, a 4-letter word is worth 1 point; a 5-letter word is worth 2 points; 6-letter words are worth 3; 7-letter words are worth 4; and so on. The player enters a blank line when they're done finding words, which signals the end of the human's turn.
Once the human player is done entering words, the computer then searches the entire board to find the remaining words (that is, the words missed by the human player). The computer earns points for each remaining word found that meets the requirements (minimum length, contained in English lexicon, not already found, and can be formed on board). If the computer's resulting score is strictly greater than the human's, the computer wins. If the players tie or if the human's score exceeds the computer's, the human player wins.
You can find all words on the board using recursive backtracking. The idea is to start from a given letter cube, then explore neighboring cubes around it and try all partial strings that can be made, then try each neighbor's neighbor, and so on. The algorithm roughly looks like the following:
for each letter cube c: mark cube c as visited. // choose for each neighboring cube next to c: explore all words that could start with c's letter. // explore un-mark cube c as visited. // un-choose
We have provided you with a file bogglemain.cpp
that contains the program's overall main
function. The provided code prints an introduction message about the game and then starts a loop that repeatedly calls a function called playOneGame
. After each call to playOneGame
, the main
code prompts to play again and then exits when the user finally says "no". The playOneGame
function is not implemented; you must write it in boggleplay.cpp
. In that same file, you can place any other logic and helper functions needed to play one game. You may want to use the getYesOrNo
function from simpio.h
, which prompts the user to type yes/no and returns a bool
.
One aspect of the console UI is that it should "clear" the console between each word the user types, and then re-print the game state (including the board, words found so far, score, etc.). This makes a more pleasant UI in which the game state is generally visible at the same place on the screen at all times during the game. See the provided sample solution for an example. Use the Stanford Library's clearConsole();
function from console.h to clear the screen.
The playOneGame
function (along with any sub-functions it calls within the same file) should perform all console user interaction, such as printing out the current state of the game. No other file should have cout
or user/file input.
But boggleplay.cpp
is not meant to be the place to store the majority of the game's state, logic, or algorithms. Your boggleplay
file will interact with a class you will write named Boggle
, described in subsequent sections. We describe a partial set of methods that your Boggle
class must have. The intention is that your boggleplay
code will call all of these methods to help achieve the overall task of playing the game. For example, no recursion or backtracking should take place in boggleplay
; all such recursive searching should happen in the Boggle
class. If you find that your boggleplay
code is implementing a lot of complex logic itself, or that boggleplay
is never calling a particular public method from the Boggle
class, this is likely a sign that you have not divided the functionality in your code the way that we intend, which might lead to a style deduction.
Later in the spec we will describe a graphical user interface (GUI) that your Boggle game must display. As much as possible, the code to create and interact with this GUI should be in your boggleplay.cpp
file. The one exception is the code to highlight and un-highlight letter cubes on the GUI while your algorithms are searching for words typed by the human player. Highlighting should be done in the Boggle
class, because it would be very difficult to separate that code out of the recursive backtracking algorithms that are defined in the Boggle
class.
The majority of your code should be in the Boggle.h / Boggle.cpp
files, which should contain the implementation of a Boggle class. A Boggle
object represents the current board and state for a single Boggle game, and it should have member functions to perform most major game functions like finding words on the board and keeping score. Declare all Boggle class members in Boggle.h
, and implement their bodies in Boggle.cpp
. We provide you a skeleton that declares some required members below that your class must have.
const
if it does not modify the state of your Boggle
object. Review all of your functions (the ones provided below, and any others you choose to add to your class) and make them const
as much as possible.
Boggle Method | Description |
---|---|
Boggle(Lexicon dictionary, string boardText)
|
In this constructor you initialize your Boggle board to use the given dictionary lexicon to look up words, and use the given 16-letter string to initialize the 16 board cubes from top-left to bottom-right. If the string is empty, you should generate a random shuffled board. Your method should be case-insensitive; it should accept the board text whether it is passed in upper, lower, or mixed case. |
b.getLetter(int row, int col)
|
In this function you should return the character that is stored in your Boggle board at the given 0-based row and column. If the row and/or column are out of bounds, you should throw an int exception (use the throw function and pass in the value that was invalid).
|
b.checkWord(string word)
|
In this function you should check whether the given word string is suitable to search for on the board: that is, whether it is in the dictionary, long enough to be a valid Boggle word, and has not already been found. You should return a boolean result of true if the word is suitable, and otherwise you should return false . Your method should be case-insensitive; you should properly verify the word whether it is passed in upper, lower, or mixed case.
|
b.humanWordSearch(string word)
|
In this function you should perform a search on the board for an individual word. If the word can be formed, you should add it to the human's set of found words. Your function returns a boolean result of whether the word can be formed. Your code for this function should use recursive backtracking. As each cube is explored, you should highlight it in the GUI to perform an animated search with a 100ms delay (see GUI section). If the word is unsuitable, you should not perform the recursive search. Your method should be case-insensitive; you should properly search for the word whether it is passed in upper, lower, or mixed case. |
b.computerWordSearch()
|
In this function you should perform a search on the board for all words that can be formed (that have not already been found by the human player), and return them as a Set of strings. Your code for this function should use recursive backtracking. Though similar to your human search, this is different because you should look for all words and not perform any animation; therefore its code should be implemented separately from humanWordSearch . The words in your set should be all uppercase.
|
b.getScoreHuman()
|
In this function you return the total number of points the human player has scored in the game so far as an integer. This total is 0 when the game begins, but whenever a successful human word search is performed, points for that word are added to the human's total score. |
b.getScoreComputer()
|
In this function you should return the total number of points the computer player has scored in the game as an integer. This total is initially 0 when the game begins, but after a computer word search is performed, all points for those words are added to the computer's total score. |
ostream& << b
|
You should write a << operator for printing a Boggle object to the console. The operator should print only the 4x4 grid of characters representing the board as four lines of text. It should print the board text entirely in uppercase.
|
Case sensitivity: Your methods that accept strings must be case-insensitive; they should work with upper, lower, or mixed case. This should be enforced in your program by the Boggle
class, not by the boggleplay.cpp
code.
Adding your own member functions: In some past assignments, we gave you a complete, exact list of the functions to implement. In this assignment, we are asking you to come up with some of the member functions. The Boggle
class members listed above represent a large fraction of that class's behavior. But you can, and should, add other members to implement all of the appropriate behavior for this assignment. Your added members should be public
if they are to be called directly by the boggleplay.cpp
code, and private
otherwise. You must also decide which code and/or data should go in boggleplay.cpp
, and which should go in the Boggle
class. Part of the challenge of this assignment is learning how to design a class and console UI client effectively. Remember that each member function of your class should have a single, clear, coherent purpose.
Here are some suggestions for good member functions to put in your Boggle class:
boggleplay.cpp
file should do all console I/O, your Boggle
class should have convenient functions for boggleplay
to call so that it doesn't need as much complex logic. boggleplay
should not contain any recursion or backtracking; all such recursive searching should happen in the Boggle
class.boggleplay
code needs to be able to display various aspects of the game state, such as all words that have been found by the each player, along with the players' scores. The Boggle
class should keep track of such things, NOT boggleplay
. The boggleplay
code should ask the Boggle
class for this information by calling public functions on it, which should return appropriate data to the caller. Note that the Boggle
class itself should not contain any output statements to cout
; let boggleplay
do that.const
if it does not perform modification of the object's state.private
if it is used internally and not to be called by the client. (This is called a "helper".)Boggle
class that directly return internal data structures in a way that allows the client to make direct modifications to them. (This is called "representation exposure" and is considered poor style.)Member variables: We also have not specified any of the private member variables that should go inside the Boggle class; you must decide those yourself. Here are some thoughts about data members that your class might need:
private
data member if it is only needed by one function; make it local. Making a variable into a data member that could have been a local variable or parameter will hurt your Style grade.Boggle
object should be private.
Searching: You don't want to visit the same letter cube twice during a given exploration, so for the search algorithm to work, your Boggle
class needs some way to "mark" whether a letter cube has been visited or not. You could use a separate structure for marking, or modify your existing board, etc. It's up to you, as long as it is efficient and works.
Please note that efficiency is very important for the part of your program that performs this search. It is important to limit your search to ensure that the process can be completed quickly. If written properly, the code to find all words on the board should run in around one second or less. To make sure your code is efficient enough, you must perform the following optimizations:
Lexicon
data structure to store the English dictionary, and do not needlessly copy the Lexicon
.Lexicon
has a containsPrefix
function that accepts a string and returns true
if any word in the dictionary begins with that substring. For example, if the first cube you examine shows the letter Z and your algorithm tries to explore one of its neighbors that shows an X, your path would start with ZX. In this case, containsPrefix
will inform you that there are no English words that begin with the prefix "ZX". Therefore your algorithm should stop exploring that path and move on to other combinations.As a required part of this assignment, you must also add a graphical user interface (GUI) to your program.
bogglegui.h
in your code, then call the functions below:
GUI Function | Description |
---|---|
clearHighlight()
|
Sets all letter cubes to be un-highlighted. (See setHighlighted.) |
initialize(int rowCount, int columnCount)
|
Starts up the GUI and displays the graphical window. The board is drawn with empty squares and scores are 0. If called again, resets the board (see reset). Throws an error if rows or cols is not a positive integer from 1-6. |
isInitialized()
|
Returns true if initialize has already been called. |
labelCube(int row, int col, char letter, bool highlighted)
|
Sets the given cube to display the given character. Rows and columns have 0-based indexes with (0, 0) at top-left. If true is passed for the optional highlighted parameter, the cube is drawn with a colored highlight (useful to show progress of word searches). The highlight will remain until turned off. Throws an error if letter is not a letter or space.
|
labelAllCubes(string letters)
|
Sets all letter cubes to display the characters from the given string. For example, "ABCDEFGHIJKLMNOP" would label cube (0, 0) with 'A', cube (0, 1) with 'B', and so on. The string can contain other characters such as whitespace, line breaks, etc., which will be skipped over. All cubes are un-highlighted after a call to this function. Throws an error if letters does not contain the correct number of alphabetic letters for the board.
|
recordWord(string word, Player player)
|
Displays that the given player has found the given word string on the board. This function does not check word validity, e.g. that the word is not already shown, can be formed on the board, is in the dictionary, etc. That is up to you. The player parameter indicates which player found the given word; the value you pass should be either BoggleGUI::HUMAN or BoggleGUI::COMPUTER .
|
reset()
|
Sets the GUI window back to its initial state, with the letter cubes blank and unhighlighted, the scores both at 0, and no solved words shown on the screen. |
setAnimationDelay(int ms)
|
Sets a pause/delay of the given number of milliseconds. After calling this, subsequent calls to setHighlighted or to labelCube that have highlight set to true will trigger a pause. Use this to animate a word search algorithm.
|
setHighlighted(int row, int col, bool highlighted)
|
Sets the given letter cube to be highlighted (true) or un- highlighted (false). |
setScore(int score, Player player)
|
Sets the GUI's score display for the given player to the given number. The GUI does not know anything about scoring rules for Boggle; it accepts any integer. The player parameter indicates which player found the given word. The value you pass should be either BoggleGUI::HUMAN or BoggleGUI::COMPUTER .
|
setStatusMessage(String status)
|
Displays a status message in the bottom part of the window. Useful for showing messages such as telling the user that they have found a word, etc. |
shutdown()
|
Closes the GUI window and frees memory associated with the GUI. |
The functions of the GUI are enclosed in a namespace so that they do not conflict with any other global function names in your program. To call one of them, you must prefix the function's name with BoggleGUI::
, like so:
// records the word "hello" for human player BoggleGUI::recordWord("hello", BoggleGUI::HUMAN);
You must call the GUI's setStatusMessage
function to display information about the game state during play. Messages like "It's your turn!", "You must enter an unfound word ...", "That word can't be formed", "You found a new word", "It's my turn", "You defeated me", and "Ha ha ha, I destroyed you" should be shown. These are the same messages that display at the top of the text console on each turn. See the runnable sample solution for more details.
In a project of this complexity, it is important that you get an early start and work consistently toward your goal. To be sure that you're making progress, it also helps to divide up the work into manageable pieces, each of which has identifiable milestones. Here's a suggested plan of attack that breaks the problem down into six phases:
shuffle
function and/or the randomInteger
function from random.h
to help you make random choices. Add an option for the user to force the board configuration, as illustrated by the sample application.Make sure to extensively test your program. Run the sample solution (top of the page) to see the expected behavior of your program. When in doubt, match the behavior of the sample solution.
Congratulations—that’s all! You are done. Now consider adding extra features.
boggleplay.cpp
functions, which set up the game and start the play.