Nifty Boggle
Boggle stands out in our minds as one of our biggest success stories
in CS2 assignments. Stanford and Duke have both been using Boggle in
the intro courses since the early 1990s. With our 10 years of
experience, we have found lots of neat ways to put the game to work in
teaching our students nifty things.
How the game is played
A Boggle board contains 16 letter cubes randomly arranged in a 4x4
grid and the goal of the game is to form words by tracing paths
through adjacent cubes without re-using letters. Adjacency can be
horizontal, vertical, or diagonal. The original game pits multiple
players against one another in real-time, each attempting to find more
words than the other players. In a computer adaption, it might become
a single human player versus a computer or a multi-player version,
with or without networking.
The assignment niche
At Stanford, we assign Boggle as our "hard" recursion assignment in
CS2, usually after an earlier warm-up assignment of solving simpler
recursive problems. Knowing that recursion is one of the more
difficult concepts for our students to master, we want an assignment
that really hammers on recursion with little else to distract
them. The meat of this assignment is implementing the recursive
searches and outside of that core, there is little additional busy
work (a little code for dice shuffling, handling user input, scoring,
not much else). We have typically provided our students with the
graphics pre-written and a black-box implementation of a lexicon to
keep them focused on the recursive task.
A tour of the algorithms and implementation options
String-driven search. One part of the task can be having
their program confirm that a user-entered word is valid and
highlighting it on the board. Verifying the word is in the dictionary
and hasn't been used before is trivial, the more interesting job is
determining where the word can be formed on the board. This algorithm
is similar to flood fill/maze escape, starting from a location and
examining neighboring positions. The recursive solution is elegant and
non-trivial -- there are interesting issues in correctly implementing
the backtracking, properly marking/unmarking cubes to avoid
duplication, and so on. You might represent the board as a 2-d array
(and thus have to deal with some of the messiness of accessing
neighbors and the special cases for cubes along the board edges) or
convert to the isomorphic undirected graph and use standard
depth-first serach. Because of its fast-fail nature, searching for a
string this way is quite efficient, on average examining about only 24
partial paths.
Board-driven search. Once the user has exhausted their
patience and/or vocabulary, the computer takes over and finds all
remaining words on the board. There is no cleverness or heuristic
here, just brute-force exhuastive recursion over all paths through the
board, checking with the dictionary to identify those that are words.
There about 12 million distinct paths through a 4x4 Boggle board, so
it can be time-consuming to check them all. The simple addition of an
IsPrefix predicate to the dictionary allows the search to avoid
wasting time examining paths down dead-end prefixes such as "qxz". With
prefix-pruning, the board-driven search only examines about 5,000
viable paths, and finishes in a blink of an eye.
Dictionary-driven search. Now think of it this way: the
computer player's task is to find the intersection between paths on
the board and words in the dictionary. Although it seems natural to
drive that search by iterating over the board looking up paths in the
dictionary, it's also possible to flip things arond. It was Owen
Astrachan of Duke University (mailto: ola@cs.duke.edu) who suggested this wacky idea about
iterating over the words in the dictionary, looking up each on the
board. If you already have a working string-driven search,
implementing the computer player this way is a snap! Is that really
tractiable? Given the phenomenal growth of cpu power, it's actually even
downright zippy. The word list we use at Stanford is about 100,000
words, examining about 24 partial paths for each (via a string-drived
search) brings us to a total of 2.4 million, but on my computer it was
only roughtly 4x the time of the board-driven alternative (which
itself is so fast to almost be untimable). Given the large number of
string-driven searchs conducted, it creates incentive to revisit the
code to see where you can shave off any time. Switching to a letter-to-position mapping with fast adjacency
features can further improve the dictionary-driven search to be
basically in the same league as the board-driven. Who would have
thought?
What makes it so nifty
First and foremost, the lovely recursive properties are
prominently featured and have several variations to explore.
There are neat opportunities to compare and contrast the
tradeoffs of different board representations, the various algorithms,
space-for-time, etc.
The result is satisfying and impressive. Students are
thrilled to have written a program that so soundly crushes them in
round after round of play. I have several screenshots students have used to document the rare occasions on which they have managed to edge out the computer. This tells me they
spend a lot more time testing this one than they do their other assignments. :-)
It's a nice bonus that the game has attractive visual qualities and that it emphasizes verbal strengths.
Resources
Here are some resources that might help you adopt this program for
your class. I have solutions in C and Java which you are welcome to ask me for. (I won't put them up here in case, your or my students are searching the web to avoid doing their work :-)
Contact info
Julie Zelenski
Department of Computer Science
Stanford University
mailto: zelenski@cs.stanford.edu
This page in support Nick Parlante's ACM SIGCSE Symposia 2002 Panel on Nifty Assignments. Other nifty assignments are available!
Last updated: March 5, 2002.
