Heesch Numbers of Unmarked Polyforms
After a few years of not writing about the subject here, I’m happy to offer an update on Heesch numbers! If you want to save time, you can skip right to the paper I wrote, or experiment with the associated dataset.
Back in 2017, I wrote a series of four posts about Heesch numbers. If you like, you can get acquainted with the subject by having a look at the first post in the series. Briefly, a shape’s Heesch number is the number of times you can surround the shape by layers of copies of itself without copies overlapping or enclosing holes. In an ill-timed coincidence, these layers are usually known as “coronas”, a usage that predates COVID by many years.
Shapes with finite Heesch numbers live on the edge between order and chaos. Their boundaries are well-behaved enough to permit one or more coronas, but not so nice that they tile the plane out to infinity. We don’t know a lot about how to find shapes with interesting Heesch numbers, or even what Heesch numbers are possible. Until last year, I would have told you that the longstanding all-time record was Casey Mann’s shape with Heesch number 5. But I’m delighted to report that earlier this year, Bojan Bašić revealed a new shape with Heesch number 6! How high can these numbers go?
One of the main topics I explored in 2017 was Heesch numbers for families of simple shapes. I focused mostly on polyominoes (shapes made by gluing squares together), though I also wrote briefly about polyiamonds (made from equilateral triangles). Given a polyform known not to tile, at the time I computed a shape’s Heesch number using a brute-force search with backtracking. Such an algorithm is a bit like exploring a maze: every time you come to a branch, you try the first path you see. If that choice eventually allows you to reach the exit, great! But if you end up in a dead end, you back up to that branch and try the second path instead, and so on. If you do this consistently everywhere, remembering your choices at branches, you eventually find the exit or discover that no path leads to it. Translating this algorithm to surrounding shapes, every edge of the shape is a fork in the road, and you can choose any legal way to attach a new neighbouring shape to cover that edge. Any given choice might limit future options and lead to a dead end, in which case you have to choose a different neighbour placement. Eventually you either find a surround or discover that there isn’t one. To compute a shape’s Heesch number, you have to check if any surround can itself be surrounded, and so on for each successive corona.
That’s a painfully expensive process! It’s easy to get stuck in a kind of backtracking hell. There could be a funny wiggle far out along the shape’s boundary that always prevents the shape from being surrounded, but you might need to explore a vast garden of forking paths that all lead to that dead end. The pain is further compounded when exploring higher coronas: proving that a shape has Heesch number 1 involves generating all possible surrounds of it, just to establish that none of them can be surrounded by a second corona. A better algorithm would teleport from point to point around the shape’s boundary, finding features of its boundary that limit how coronas can form. It’s a bit like cordoning off some of the branches in a maze so you know never to explore them. But it’s quite difficult to know where to look for these features, and that still doesn’t help with higher coronas.
And so, my 2017 enumeration has serious problems. I could compute Heesch numbers only for small shapes, and even then computation time varied wildly, from a fraction of a second to weeks or longer. Some computations never produced an answer, forcing me to leave some polyominoes unclassified. And my code had other bugs, causing it to report the wrong Heesch number for some shapes. Yuck.
Computing Heesch numbers with a SAT solver
All that changed in 2019. In a thread on Facebook, Bram Cohen suggested that a SAT Solver could be used to compute Heesch numbers in a way that would likely outperform any hand-tuned algorithm. A SAT Solver is a tool that takes a Boolean formula as input (a bunch of variables, combined together with AND, OR, and NOT operations), and tells you whether there’s any way of choosing true and false values for the variables so that the whole formula comes out true. Bram’s idea was that you could translate the question “does this shape have Heesch number at least n?” into a Boolean formula whose variables represent all possible locations for copies of the shape, and let the SAT Solver grind through these variables, shaking out a subset that defined a configuration of legal coronas.
A SAT Solver isn’t a silver bullet: in the worst case, it can still get stuck in backtracking hell. But these tools are highly optimized, and are really, really good at jumping around the input problem, finding ways to limit the number of branches to explore. And that’s where the SAT Solver will win here. Any heuristics I could implement would be motivated by (and limited by!) a geometric interpretation of the problem. The SAT Solver doesn’t care about geometry: all it knows about is Boolean variables and how to avoid unnecessary work. I love the idea some problems can be solved more easily by being dumber, by thinking less about the intricacies of the problem domain. It reminds me of counterintuitive advice from math contests like the Putnam: sometimes, the best strategy for solving a problem is to solve a harder, more general problem instead. Quanta Magazine has a good article about using a SAT Solver in the context of a different mathematical problem.
Bram’s suggestion was spot-on. He offered a first version of the translation from geometry into Boolean logic, which we then refined by email. (I have since learned that Bram often swoops in, drops a brilliant idea into someone’s lap, and then rides off into the sunset.) The SAT Solver I used, CryptoMiniSat, has no trouble chewing through the computation of Heesch numbers of polyominoes. Its performance is extremely reliable too: on average it requires about 0.15 seconds per shape, and never more than about a minute for shapes with high Heesch numbers, completely avoiding the worst of backtracking hell. And a SAT-based approach generalizes easily to polyiamonds and polyhexes (made from hexagons) too! So, since 2019 I was able to correct errors in my previous enumeration, do away with all unclassified shapes, and extend the enumeration to higher polyominoes, polyiamonds, and polyhexes. As of this writing, I’ve computed Heesch numbers for all polyforms up to 19-ominoes, 17-hexes, and 24-iamonds.
If you’re interested in all of the technical details, I’ve written a paper on this search, which is available on arxiv.org. I’m also making a dataset available containing a few thousand polyforms and their Heesch numbers, as both text descriptions and drawings showing coronas. Below, I summarize a few of the main results.
Of course, I have to start with a new table showing Heesch numbers of polyominoes:
Heesch numbers of polyominoes, no holes in the outermost corona
|n||non-tilers||H = 0||H = 1||H = 2||H = 3||Drawings|
What a difference! Whereas before I couldn’t even deal with all 700000 14-ominoes, here I’ve handled 1000 times as many shapes. The search even turned up the two smallest polyominoes with Heesch number 3, when n = 17. In the paper I offer a second table, giving alternate Heesch numbers when holes are permitted in the outermost corona. Click on the link in the rightmost column for a PDF from the dataset containing either all non-tilers (0-up) or shapes with Heesch number 2 and higher (2-up).
If tables of numbers make your eyes glaze over, let’s pause to look at a couple of examples. Here are some sample polyominoes with increasing Heesch numbers: a 7-omino with H = 1, a 9-omino and a 15-omino with H = 2, and two 17-ominoes with H = 3. Remember that none of these shapes tile the plane!
But wait, there’s more. Here are the Heesch numbers of hole-free polyhexes. There are a half dozen with Heesch number 4!
Heesch numbers of polyhexes, no holes in the outermost corona
|n||non-tilers||H = 0||H = 1||H = 2||H = 3||H=4||Drawings|
In the drawings below, the top row shows 6-hexes with Heesch numbers 1 and 2, the 7-hex with Heesch number 3, and the 11-hex with Heesch number 4.
And completing the enumerations, here’s the table for polyiamonds, including a single example with Heesch number 4:
Heesch numbers of polyiamonds, no holes in the outermost corona
|n||non-tilers||H = 0||H = 1||H = 2||H = 3||H=4||Drawings|
Below are the 7-iamond with Heesch number 1, three 10-iamonds with Heesch number 2, a 10-iamond with Heesch number 3, and the 20-iamond with Heesch number 4.
I’m glad these enumerations are out there in the world. Casey Mann’s work on Heesch numbers of polyforms with markings is excellent, but I felt sad for the poor unmarked polyforms, which deserved to be explored.
I might try extending the enumerations above, but I’m not excited about the prospect given that the next step for any of the polyform types will burn a lot of CPU cycles, at least without another quantum leap in performance. I’m more interested in looking for other kinds of shapes that might lead to high Heesch numbers. I have a student working on the subject with me this summer (following yet another lead suggested by Bram), so stay tuned for new results!
Leave a Reply