I recently checked out the Scramble application on Facebook, which is a knock-off of Boggle. It’s a fun diversion, even though I usually get my ass kicked. There’s an annoying chat window there, too, and invariably someone will accuse someone else of cheating, at which point a number of people will pipe up with “how would you cheat?”
This got me thinking…how *would* you cheat? You’d just have to write a Scramble puzzle solver that spit out all the words in on the board. That sounded like a fun problem. I hadn’t done anything with recursion in a while, so I gave it a go. Below is what I came up with. You’ll need a word list to run it. I originally used /usr/share/dict/words, but it was missing a lot of valid words (I think it only has base words, no plurals or tenses). So I stole the scrabble word list from the Debian scrabble package, which worked much better.
Anyway, here you go:
I did try this out a couple times on Scramble and won handily. There’s really not much fun in that, though.
Update: I posted this in one of the comments below, but I’ll put it here as well to make sure everyone sees it: This was really just an exercise in coming up with a fun algorithm, and is primarily intended for programmers. If you’re just looking to cheat at Boggle/Scramble, there are plenty of web sites that will help you with that, and with a lot less effort.
