CSC 427: Data Structures and Algorithm Analysis
Fall 2004
HW6: Hash Sets and Backtracking
Boggle (® Hasbro) is a game in which a 4x4 grid of letters is randomly chosen,
and then the
players try to identify as many words in that grid as possible. Words can be formed
by any sequence
of adjacent letters in the grid. For example, consider the following grid.
<![CDATA[
c k s z
x o t h
d g r n
z n a m
]]>
The word "sock" is formed starting at the letter "s" in the top row, moving down
diagonally to
the "o", moving up diagonally to the "c", and finally moving right to the "k". Note
that letters
can be connected horizontally, vertically, and diagonally. The same occurrence
letter may not be
used more than once in the same word, however. Thus, "tot" is not a valid word in
the above grid.
A player earns points for each word found in the grid, with an n-letter word earning
n points. For
example, "so" is worth 2 points while "strand" is worth 6 points.
Your program should have the following features:
- It should place random letters in the grid and display it.
- It should then allow the user to enter words that they identify from the grid.
If the entered
word is valid, i.e. it can be found in the grid and is listed in the specified
dictionary, then they
should be awarded the correct number of points. Invalid words, i.e. words that don't
appear in the
grid or are not listed in the dictionary, result in one penalty point each (with
appropriate
messages). Similarly, the user should not be able to earn points twice on the same
word (even if it
appears more than once in the grid).
- Once the user finishes entering words, the program should print their total
score, and ask them
if they would like to see a listing of all of the words they missed. If so, the
program should
print out all of the valid words that were not entered by the user.
An online dictionary of words is provided for you in the file dict.txt. Since this file contains over 58,000 words,
efficient storage
and access is imperative. You should use a hash_set to store and search for
words as
needed.
Sample execution:
<![CDATA[
Welcome to Dave's online Boggle game.
I will show you a 4x4 grid of letters, and you are to find as many words
as you can by connecting letters in the grid (you can connect letters
horizontally, vertically, or diagonally). The longer the word, the more
points you earn. Let's play:
l s q t
r v k b
v u m w
k k a w
Enter your words (terminate with '*'):
ma
CORRECT! 2 points.
maw
CORRECT! 3 points.
skum
THERE IS NO SUCH WORD. -1 point.
rum
CORRECT! 3 points.
maw
YOU ALREADY GOT THAT WORD.
mum
THAT WORD IS NOT ON THE BOARD. -1 point.
*
TOTAL SCORE = 6
Do you want to see the words you missed? (y/n) y
a
am
auk
mu
]]>
Hint 1: Think OOP. For example, instead of just representing the grid
of letters as a
2-dimensional array or vector, define a class (e.g., BoggleBoard) that
combines the grid
with its basic operations. Such modularity will help to manage the complexity of the
program.
Hint 2: Since you will have to display all of the valid words in the grid
at the end (at
least those not entered by the user), it probably makes sense to find all of the
valid words up
front and store them in a hash_set. The grid can be searched via recursive
backtracking,
using the functions below.
<![CDATA[
bool BoggleBoard::contains(string word)
{
for (int r = 1; r <= BOARD_SIZE; r++) {
for (int c = 1; c <= BOARD_SIZE; c++) {
if (contains(word, r, c)) {
return true;
}
}
}
return false;
}
bool BoggleBoard::contains(string word, int r, int c)
{
if (word == "") {
return true;
}
else if (board[r][c] != word[0]) {
return false;
}
else {
char safe = board[r][c];
board[r][c] = '*';
string rest = word.substr(1, word.length()-1);
bool result = (contains(rest, r-1, c-1) || contains(rest, r-1, c) ||
contains(rest, r-1, c+1) || contains(rest, r, c-1) ||
contains(rest, r, c+1) || contains(rest, r+1, c-1) ||
contains(rest, r+1, c) || contains(rest, r+1, c+1));
board[r][c] = safe;
return result;
}
}
]]>