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.

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!

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

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

Where can I find the wordlist that they used?

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