4 ms·
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 B
by sireat 1y ago
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?
- rahimnathwani 1y agoYou might find the answer in the README: https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREADME.md https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREA... Scroll down to 'Sum/Choice trees' or Ctrl+F max_bound
- danvk 1y agoThere are simpler ways to calculate a bound that don’t involve trees. You can read about the sum and max bounds in the WIP paper: https://github.com/danvk/hybrid-boggle/blob/main/paper https://github.com/danvk/hybrid-boggle/blob/main/paper There are some examples in these old posts: - https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/index.html https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/inde... - https://www.danvk.org/wp/2009-08-11/a-few-more-boggle-examples/index.html https://www.danvk.org/wp/2009-08-11/a-few-more-boggle-exampl... These bounds are pretty effective at finding the global max for 3x3 Boggle, but 4x4 is a lot bigger. There is a mapping from Boggle optimization to ILP, but I’ve seen no evidence that this is an efficient way to solve it. I’ve been told that branch and cut is usually better than branch and bound, but I don’t know whether it’s applicable to Boggle.