# 08.04.09

## Solving Boggle by Taking Option Three

Posted in boggle at 6:18 pm by danvk

There is exciting news to report in the land of Boggle!

Last we spoke about Boggle, we used Simulated Annealing to get at the question “what is the highest-scoring Boggle board?”

We found a board with 3625 points on it this way. It would have been nice to say that it was the best of all possible boards, but that would have been too rash. While it is a very good board and I have never seen a higher-scoring one, that doesn’t mean there isn’t one out there. Maybe I’ve just been looking in the wrong places.

To prove that the 3625-pointer is the best board, we’d need to show that every other board scores fewer points. In a previous post, I estimated that there were 2^69 possible boggle boards. At 10,000 boards/second, this would take 1.9 billion years of compute time!

When you run up against a computationally intractable problem, there are a few standard ways to deal with it:

1. Give up.
2. Come up with a brilliant new algorithm to solve the problem more quickly.
3. Solve a simpler problem.

Option 1 is the easiest. Option 2 is the hardest. And option 3 is the compromise we’ll be taking for the next few danvk.org boggle posts. Our simpler problem today: 3×3 boggle.

If we drop seven letters (4×4 – 3×3 = 7), we’re left with only 26^9 / 8 ≅ 2^39 boards to consider. If we can achieve 10,000 boards/sec, this would be just over two years’ worth of computation. That’s still a lot, but it’s much more reasonable than 1.9 billion years!

I believe I have solved the 3×3 boggle problem using an approach that is only slightly more clever than this. I used simulated annealing to find very high-scoring 3×3 boards. This was the best one I found, along with its 4×4 best board buddy:

 p e r l a t d e s 545 points

 p e r s l a t g s i n e t e r s 3625 points

It’s worth noting that the optimal 3×3 board has a 2×3 region in common with the 3625 point 4×4 board.

In the next post we’ll talk about how I showed that this board was higher-scoring than all 2^39 others in significantly less than two years (it took one day). As a teaser, I’ve included all the 3×3 boards with more than 500 points worth of words below the fold.

I’ve made the boards fit on a single line by reading them like a book: left to right, then top to bottom.

Board Score
perlatdes 545
pelsartes 542
delratpes 540
lepsartes 536
tepsarles 528
selratpes 528
legsartes 527
berlatdes 526
relsatpes 524
perlatces 523
derlatpes 522
telsarpes 520
parletdes 520
lersatpes 520
saltipres 518
tepsarled 514
tegsarles 514
tedsalrep 514
repsalted 514
ledsartep 514
pelsatres 513
tegsarlep 511
lepsarteg 511
tapselres 510
serlitpas 508
lecsartep 508
tedsarleg 507
persatles 507
legsarted 507
tepsarleg 505
selratdes 505
legsartep 505
canretdes 505
canretdes 505
pinlatres 504
nirgatres 504
lecsartes 504
serlatpes 503
letrasdep 503
derlitpas 503
derlatbes 502
cerlatpes 502
cerlatpes 502
retgasnil 501
nilgasret 501
metparles 501
merpatles 501
tedsarlep 500
tapselred 500
redseltap 500
pecsartes 500
lepsarted 500

As always, this using the Enable2K word list. Code can be found here

## 1 Comment

1. August 8, 2009 at 3:03 pm

[...] points (it contains words like ‘crypt’ and ‘gypsy’). We’ve already found a single board that has 545 points on it. So we can eliminate this entire class of 794 billion [...]