Fantastic and fun achievement danvk!

Solving Boggle would be a welcome addition to my Branch and Bound examples.

I teach Algorithms course and my Branch and Bound lecture usually involves solving integer linear optimization problems. Those are quite dry.

Now for the Branch and Bound to work you need what I informally call "cheat code". That is we need a way of solving a relaxed - easier version of the problem quickly . Quickly meaning with less time complexity.

So what is the approach / key insight to calculate upper and lower bound estimates in Boggle?