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.