01.25.14

What up with Boggle?

Posted in boggle at 1:47 pm by danvk

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!
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.