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

Permalink