His blog post announcing it: https://www.danvk.org/2025/04/23/boggle-solved.html
FT article: https://archive.ph/siaAO
His blog: https://www.danvk.org/blog.html
> Driven “by the thrill of discovery”, Vanderkam has searched for this board, essentially alone, since 2004. He would scrape together computing time on Google’s hardware for heavy Boggle computation, all along documenting his efforts on his blog.
> “As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said.
> “As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said.
For context, many people are interested in finding high-scoring Boggle boards, usually via simulated annealing, hillclimbing, or genetic algorithms. But so far as I can tell, I'm the only one interested in _proving_ that a particular board is best. Doing that was the new result here.
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?
There 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
There are some examples in these old posts:
- https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/inde...
- 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.
You might find the answer in the README: https://github.com/danvk/hybrid-boggle/blob/main/paper%2FREA...
Scroll down to 'Sum/Choice trees' or Ctrl+F max_bound
It was a fun surprise to see this story on the front page of this morning's Financial Times. It's very unusual in my experience for this sort of thing to be picked up by the mainstream media before it's on HN or similar. I wonder how the FT reporter came across the story.
"Lone coder" here. I reached out to Ollie (the FT reporter) because he'd written a book (Seven Games) about computers and games, so I thought the Boggle story might interest him. It did!
Nice work! I love an "impossible" problem that falls to bounding estimates like this one does. There was a surprisingly lot of work done in protein folding that had similar sorts of techniques to eliminate structures that would either never happen or would self destruct if they did kinds of things.
Congratulations, Lone Coder! Both for the exciting work and for getting it on the front page of the FT. Just amazing on both counts.
I love that book. Good choice and congratulations on your find.
This was posted on HN about a month ago: https://news.ycombinator.com/item?id=43774702
Thanks! Macroexpanded:
After 20 years, the globally optimal Boggle board - https://news.ycombinator.com/item?id=43774702 - April 2025 (23 comments)
How did that spend only 6 hours on HN's frontpage? I'm gonna email danvk right now
Thanks. What's particularly embarrassing is that I found that submission this morning, and read the comments on it, and then somehow forgot about its existence until you reminded me of it just now.
Thank you. I felt something must have been seriously wrong in the world that the FT knew this before any HN contributor.
The author himself was the original submitter.
> The code is a mixture of C++ for performance-critical parts and Python for everything else. They’re glued together using pybind11, which I’m a big fan of.
Nice, I'm a big fan of this combo! Hits the right balance of prototype speed plus performance.
The 192 core Google Cloud server is likely running at a fairly low frequency for power efficiency. So 5 days on it might be comparable to 1 or 2 months on a 16 core Ryzen 5950X that you can rent at hetzner.com/sb for around $100 a month. You can alternatively get an Epyc 7502P there (32 cores) for around the same price. I don't know how the speed would compare.
I have been surprised that the Boggle code runs about 4x slower on the GCP machine than on my M2 MacBook. I don’t have enough experience running CPU- and RAM-intensive cloud jobs to know whether this is normal.
Similar experience at DigitalOcean where, in 2023, I rented a VPS with dedicated cores to compute on some decent-sized dataset and it turned out to be slower than the 2012 laptop CPU that I use as my main server! That laptop has an i7-3630qm iirc, not sure what DO claimed they give you but it was slower
The storage i/o speeds were also crap (quoting myself here from the notes I made at the time) compared to what I got soon after when I bought a 70€ TLC SSD as upgrade for the laptop-server. They claim it runs on SSDs but, if it does, they're the world's cheapest bulk data SSDs or they have a bottleneck in ferrying data between the SAN and the VPS host, even for sequential r/w (that it has higher iops latency, I could understand)
At work, we sometimes use AWS GPUs for password cracking (we do security audits and sometimes find hashes). The GPUs that employees have just to play some games are faster than these and cost a lot less to operate, but we can't put customer data on private systems
For occasional problems that can be parallelised, sure, rent a hundred temporary systems at a cloud farm for two days; but in general I just can't recommend it to anyone. It costs an arm and a leg compared to cheaper providers or buying hardware yourself (if you're into being the sysadmin). The "we have a fleet of systems on stand-by for you" (so you can scale on demand) is a big premium that most seem to be unaware of that they're paying implicitly
> "As far as I can tell, I’m the only person who is actually interested in this problem"
I think this is a really interesting problem but I have to admit that if I'd heard it stated I would have guessed the answer was already known. I love the persistence on display here in spite of it being a "low status" problem. Reminds me of the recent discovery of a new largest (Mersenne?) prime, just someone getting nerd sniped and willing to spend their time and money.
> The problem is hard because examining every possible Boggle board is unfeasible. There are something like a 20-digit number of them and scoring every one — even at Vanderkam’s pacy 200,000 boards a second — would take 800mn years.
> It took 23,000 CPU hours on a high-end 192-core machine in the cloud — time worth about $1,200, across five human days.
Pardon the pun but the sheer amount of possible boards is mind boggling. Impressive how he managed to cut it down by magnitudes.
I love scrabble and boggle, but to me there is tension between just playing for points according to a certain set of rules, and playing to form nice satisfying words.. eg. in scrabble you could use all sorts of bullshit scrabble words that are in SOWPODS like "za" and "qi", but imo its sort of undignified and cheesy to do so.
Like this person, I also remembered the Notre Dame Scrabble Team fight song. I found this post by web search on the words.
https://mudcat.org/thread.cfm?threadid=45390#671943
Added: I think s/he got some of the words slightly wrong!
This is the same thing I realized when being a "game master" of the shooter matches we used to hold on my previous project. The end goal of that play was fun, not to determine who has the most technical skill. After realizing this in my head, and also implementing it as additional rules for the game, the game sessions became much more enjoyable for everyone, participation, enjoyment, and desire to return for another session was through the roof.
That said, both kinds of play has its place, in my life at least. Staying on the topic of shooters, when I play online in ranked, it's all out for me, and I enjoy that as well, in a different way. But when playing with my wife, it's never all out, always friendly.
I used to agree with you. But there's a slippery slope. At what point is a word "bullshit"? What if you simply have a better vocabulary than other players?
Our family compromise has always been, if it's valid and you know its definition (like "qi" and "za"), you can play it.
Easier rule is just to exclude two letter words, or make two letter words zero points (so you can get rid of your Qs and Zs if you wish
If you exclude two-letter words, you are also excluding nearly all overlaps and parallel plays.
I really didn't enjoy playing Scrabble with someone who knew a bunch of the two letter words. It was similar to playing Team Fortress 2 in a "pro" match rather than public. In pro matches they won't even use certain character classes at all because they're not optimal. It's a completely different game.
You just have to find people to play with who are like you. Then you'll have fun. Our family rules didn't even allow 2 letter words, for example.
Quibble: There’s only 6^16 possible sets, not 26^16.
That would only be if the dice order didn't matter. Multiply by 16! for the number of ways you can place your rolled dice in the grid.
Then you find that 26^16 is less than 6^16*16!
https://www.danvk.org/wp/2007-08-02/how-many-boggle-boards-a...
Mirror?
Posted above: https://archive.ph/siaAO