Decorate the edges so the only tilings left are the ones that never repeat
A shape on its own is a weak instrument. Two squares fit together in more ways than anyone wants to enumerate, and most of those ways lead to a boring repeating pattern. A matching rule narrows the options: mark the edges, and declare that two tiles may meet only along edges bearing the same mark.
This is the device that made the first aperiodic sets possible, and it is still how the hat proof works underneath. The decorations do not change the shapes; they change which arrangements count.
The cleanest version is Hao Wang’s, from 1961: unit squares with a colour on each side, placed without rotating or reflecting, meeting only along sides of matching colour. Wang conjectured that any set of these able to tile the plane could also tile it periodically — and observed that if that were true, there would be an algorithm deciding whether a given set tiles at all.
His student Robert Berger disproved it in 1964, with a set of 20,426 tiles, and in doing so proved the tiling problem undecidable. The three sets below are far smaller and far tamer, but they show what colours on the sides can do: force everything, decide almost nothing, or make a region impossible outright.
Choose the first tile and every other tile in the box is determined. Two tilings of any size — one per choice — and both repeat with period two going up.
Wang tiles may not be rotated or reflected — that restriction is the whole point, since it is what lets the side colours encode a rule. Hao Wang asked in 1961 whether a set that tiles the plane must also tile it periodically. Robert Berger answered no in 1964, with a set of 20,426 tiles; Emmanuel Jeandel and Michaël Rao brought the record to 11 in 2015 and proved that 10 is impossible.
Try it: Compare the three. The forced set has exactly two fillings of any box — pick the top-left tile and the rest follows, with no backtracking at all. The loose set has one free choice per row. The impossible set fits a two-by-two box in exactly one way and then fails, and the search has to back out to discover it. That last behaviour, scaled up enormously, is Berger’s proof.
The same idea runs underneath the hat. The four clusters carry edges in five classes — A, B, X, F and L — and the paper draws them in five colours. They matter for a reason that is easy to miss: the sequence of labels round a cluster is what identifies which corner of a supertile plays the part of which vertex of the cluster it stands in for.
The H tile reads X B X X B X X A X round its 9 edges. Hover a class to pick it out. Some outlines have vertices in the middle of what looks like one straight side, because the paper splits a geometric side into several labelled edges and the split is where the rule lives.
Try it: Look at where the vertices sit on H. Three of them lie in a row along what is visually one straight side, because the paper splits that side into separately labelled edges. Those splits are not cosmetic — deleting them would destroy the correspondence that lets the substitution iterate.
Calling a decoration a matching rule is a claim, and it is checkable. Take a patch, break every tile’s boundary into unit lattice steps, and for every step with a tile on both sides, look at the two labels that meet. If they are only decoration, the pairings will be varied. If they are a rule, a label will meet nothing but its own kind.
The census is taken one unit lattice step at a time rather than one labelled edge at a time, because two neighbouring tiles need not split a shared side the same way. Nothing about this is a tolerance: a segment is shared when the same two integer endpoints are walked in opposite directions, and that is either true or it is not.
Try it: Push the size up and change the seed. There are five pairings, never more, and they are A–A, B–B, X–X, F–F and L–L. The mismatch count stays at zero across every patch — thousands of shared segments, with no exceptions and no tolerance involved.
The instrument gains its third capability here: an overlay drawing the edge labels in place. It only appears when you are zoomed in far enough for the labels to be legible — below that it stands down rather than smearing five colours over the whole canvas.
Generations stop at 6, which is 242,962 tiles. The substitution keeps going — generation 7 from an H is 1,667,659 — but building that takes about 0.7 s and 25 MB, so the instrument does not offer it.
Try it: Colour the tiles flat and turn the labels on, then zoom right in. Where two tiles meet you see a single colour, because both sides agree — the census above, one edge at a time.
There is a catch that shaped the next sixty years. A matching rule is extra information — a marking, an arrow, a colour — and a purist can object that the tiles are not really doing the work. The standard response is to build the marking into the shape: replace a marked straight edge with a bump and a matching notch, so that only the right pairs physically fit. That is how the Penrose rhombs became genuine shapes rather than decorated ones, and it is why the hat, which needs no markings at all, was worth sixty years of looking.