01.25.14
What up with Boggle?
A Boggle-obsessed friend recently asked how he could read all the posts about that game on my blog. I used to include categories on every post, but removed them when I updated the design of danvk.org. The categories are still there, though! Here’s a link to the Boggle Category. It’s better to read the posts in chronological order, starting from the first.
Here they are for easy clicking:
Jan 2007 Boggle #2: The Shortest Solver
Jan 2007 Boggle #3: Succeed by not Being Stupid
Feb 2007 Tries, the Perfect Data Structure
Feb 2007 Moving Boggle to C++
Feb 2007 In which we discover that Tries are awesome
Feb 2007 One Last Boggle Boost
Feb 2007 Some Boggle Statistics
Feb 2007 Initial Impressions of D
May 2007 JRuby Performance, Yowch!
Aug 2007 How many Boggle boards are there?
Sep 2007 A Java Surprise
Feb 2009 Sky-High Boggle Scores with Simulated Annealing
Aug 2009 Solving Boggle by Taking Option Three
Aug 2009 Breaking 3×3 Boggle
Aug 2009 Some max/no mark examples
Aug 2009 A Few More Boggle Examples
Stepping back a little bit, what’s the status of my Boggle efforts?
The overall goal is to find the highest-scoring Boggle board and prove that there are no better boards out there.
I’ve solved this problem for 3×3 Boggle boards. Here’s the best board:
P E R L A T D E S
Its longest words include REPLATED and REPASTED. You can see all the words here. This board has more points on it than any other board (using the Enable2K word list) and I’ve proved it.
The 4×4 problem is much harder, though, because there are eight billion times more boards to consider! I believe that this board is the best one:
P E R S L A T G S I N E T E R S
You can see a list of all the words on it here. The longest word is REPLASTERING. I haven’t been able to prove it, though, and I haven’t put any serious time into the problem since 2009.
You can find all the Boggle-related code I’ve written on github and learn all about the algorithms and techniques by browsing posts in the Boggle Category on this blog.
Kenny said,
January 25, 2014 at 3:15 pm
Awesome! I’m not the one who’s boggle obsessed though! A coworker of mine mentioned he has a boggle solver side project and I thought he would enjoy your posts. I don’t even own the game! :-O
Richard said,
February 1, 2014 at 9:34 pm
Solving is easy. The hard part is creating a board with a bunch of words from a theme word list.
First you need to semi-random pick words that share letters from the theme word list such that they share letters. Then figure out how to place them on the board such that they allow the words to be spelled. THAT is something I have not figured out yet. Random placement on a board does not work when you have at least 8 words ….. eg: ‘margays’, ‘jaguars’, ‘cougars’, ‘tomcats’, ‘margay’, ‘jaguar’, ‘cougar’, ‘pumas’, ‘puma’, ‘tomcat’, ‘toms’, ‘tom’
Note there are under 16 letters in those words. But how to organize them in a 4×4 grid to make the majority of those words ?