A Computational Proof of the Highest-Scoring Boggle Board

This reminded me of one of my high school computer science assignments- simply to find all words in a single boggle board. And try to optimize your solution a bit. The point was to teach about recursion/backtracking and data structures. The intended solution was roughly: start at a square, check if your current prefix is a valid prefix, move to a neighbor recursively, and emit any words you find. Trying to optimize naturally motivates a trie data structure.

I found it to be at least an order of magnitude faster, though, to invert the solution: loop through each word in the dictionary and check whether it exists in the grid! The dictionary is small compared to the number of grid paths, and checking whether a word exists in the grid is very very fast, requiring not much backtracking, and lends itself well to heuristic filtering.

My first thought is that there is surely an Integer Linear Programming approach that can solve this within a few seconds using some very advanced solver like Gurobi.

These solvers can very often find the globally optimal solution - and prove that this solution is optimal - much faster than exhaustive search.

Of course they do use a smart exhaustive search by applying branch-and-bound as described in this article, but advanced solvers use, among other things, branch-and-cut where cutting planes in the solution space are generated, as well as a variety of other approaches.

One interesting thing however is that GPUs are still not particularly applicable for solvings Mixed Integer Linear Programs to sufficient accuracy. There are things like PDLP that can use GPUs to solve these problems, but they are restricted to something like 1e-4 accuracy whereas the state of the art is more like 1e-9.

My favorite part of the write-up is the first sentence after the "What if there's a bug?" section.

Fun, love word game computations! Reminds me a bit of the challenge to place the challenge to place all letters in the alphabet in as small a grid as possible, with valid words: https://gamepuzzles.com/alphabest.htm

I made a word game based on a similar concept, featuring different letters every day: https://spaceword.org

Where can I find the wordlist that they used?

Edit: Found it here: https://coursera.cs.princeton.edu/algs4/assignments/boggle/f...

Simulated annealing [1] is mentioned but not explained in the list of modifications to hill climbing. The technique roughly is: accept modifications to the board which decrease the score, with a probability inversely related to the magnitude of the decrease, and which decreases as the search progresses. This helps avoid getting stuck in local maximae.

[1] https://en.wikipedia.org/wiki/Simulated_annealing

EDIT: Somehow I didn't see that simulated annealing was mentioned by name (but not explained), ha!