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.
> 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.
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?
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.
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.
> "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.
Quibble: There’s only 6^16 possible sets, not 26^16.
Mirror?
[flagged]
[dead]
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.