Boggle™ Solver Project

Your job is to develop two simple Boggle™ puzzle solvers -- a simple brute-force solver, and a significantly more efficient solver.

TNSP
RAYJ
HINU
AACT
These puzzles are fun to play, and simple to implement. A board is easily represented as a simple string, e.g., "tnsprayjhinuaact" for the 4x4 puzzle:

"Q" is a special case. Since "q" must be followed by "u" in most English words, "Qu" appears as a single "letter" on Boggle™ cubes. For our purposes, "q" in a string means "Qu."

Resources

Exercises

BS-1: Brute-Force Solver

Create a package boggle that exports two symbols, on-board-p and solve-boggle.

Define (on-board-p word board) to take two strings, a word and a board, e.g., (on-board-p "aha" "tnsprayjhinuaact"), and return true if the word is on the board, according to the rules of Boggle™. The board length may be any perfect square, e.g., 9, 16, 25, ...

Define (read-words file) to return a list of all the words in a word-list file. It should ignore words less than 3 letters long. Use this to set a non-exported global variable to all the words in crosswd.txt. Make sure it reads 113724 words of length 3 or greater.

Define (solve-boggle board) to find all words in your global word list that are on board, according to on-board-p.

Test your code with boggle-tests.lisp. Note that the last test requires treating "q" as "qu."

Run (time (solve-boggle "atistghuiirineuoqsnrceetd")) several times to get a best case running time.

Tips:

BS-2: Fast Solver

Define (read-trie file) to return a trie of the words in a word-list file. For this exercise, simple nested lists are sufficient to represent the trie. Again, ignore words less than 3 letters long.

Apply this function to crosswd.txt and save the result in a global variable.

Redefine (solve-boggle board [trie]) to scan the board and return all words in the given trie that are on the board. trie should default to your global trie variable. The trick to doing this is to define a recursive function that starts from the letters on the board to find paths down the trie. If you start at a "b" and a neighboring cube is "x," the trie will immediately tell you that no words start with "bx." This is the source of the speed.

Test your code with boggle-tests.lisp.

Run (time (solve-boggle "atistghuiirineuoqsnrceetd")) several times to get a best case running time.

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15

Contents

Important Links