Boggle™ Solver Project
Your job is to develop two simple Boggle™ puzzle solvers -- a simple brute-force solver, and a significantly more efficient solver.
T | N | S | P |
R | A | Y | J |
H | I | N | U |
A | A | C | T |
"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
- crosswd.txt: A list of 113,809 words (warning: you may find some words offensive) from Grady Ward's Moby Word Lists at Project Gutenberg.
- boggle-tests.lisp: lisp-unit tests
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:
- First read the rules of the game. Don't worry about scoring here.
- To avoid problems with packages and character case, store words as lower-case strings.
- Be sure to compile your code before trying the large dictionary.
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.