01.28.07
Boggle!
After showing Evan my online boggle solver at work, I was inspired to start writing some blog posts on how that program works. So here goes!
Boggle is a game by Hasbro in which you try to find words on a 4×4 grid of letters. There are 16 dice with six letters apiece on them. You roll the dice into the 4×4 slots and connect them to form words. The longer the words you find, the more points you get.
You can use diagonals and you can cross your own path, but you can’t use the same die twice in forming a word:
As a CS-type, it wasn’t long before I started thinking about how to write a computer program to quickly find all the words on a Boggle board. The right way to think about the board is as a bidirectional graph:
To get all sequences of letters in a graph, we can just do a depth-first search. There will be a ton of these sequences, but most of them will be phrases like “aefbg” that aren’t real English words. So we’ll also need a dictionary to filter out the non-words. Then it’s just a matter of scoring:
| Length | Score |
|---|---|
| 1-2 | 0 |
| 3-4 | 1 |
| 5 | 2 |
| 6 | 3 |
| 7 | 5 |
| 8-17 | 11 |
Seventeen letter words are possible! Just look at the ‘inconsequentially’ board above. The “qu” die is a minor nuisance that’ll keep coming up. It’s the only die that doesn’t have just one character on each face.
Next time we’ll code up a solution in Ruby and test its performance. After that, we’ll start looking at optimizations and how to find the highest-scoring Boggle board.
danvk.org » In which we discover that Tries are awesome said,
August 7, 2009 at 5:00 pm
[...] is the sixth installment in an ongoing series about Boggle. See also 1, 2, 3, 4 and [...]