Four easy patches and one that is not

The five tessellation patches in this collection are the same construction at five different tilings. A twist polygon at every vertex of a square grid, a stretched grid, a honeycomb, a triangular grid and a rhombille tiling; every polygon turned by the same angle; the gaps filled with pleats; the whole thing clipped to a square sheet.

They differ in size — forty-nine panels up to a hundred and fifty-seven — and in the share of their letterings that agree with themselves, which runs from thirteen per cent down to nothing. That much was already measured.

What was not measured is what it costs to find a lettering that agrees with itself, and running the same search a hundred and twenty times on each one produces a table with a cliff in it.

Four patches that do not search #

On the square patch every one of the hundred and twenty runs finishes between twenty-five and thirty-six nodes, with the middle at twenty-seven. The elongated patch runs thirty-two to thirty-nine. The hexagonal, thirty-nine to fifty-one. The triangular, thirty-nine to fifty-three.

Those are not searches. A node is a point at which a letter was set or taken back, and a patch of forty-nine panels needs roughly forty-nine decisions before every crease has a letter; twenty-seven nodes with propagation filling in the rest means the search walked straight to an answer and never revised anything. The variation across a hundred and twenty seeds is the difference between guessing well and guessing slightly less well on the way down a corridor with no turnings.

The four patches also differ in size by a factor of nearly two, and their costs track the size almost exactly. Cost per panel: 0.55, 0.55, 0.56, 0.54. That is not a scaling law; it is the observation that the search does one thing per panel, which is what a search that never backtracks does.

The fifth #

The rhombille patch is the same construction on a tiling with two kinds of vertex — six rhombi meeting at a lattice point, three at a triangle’s centre — and it behaves completely differently.

Best run: eighty-four nodes. Middle run: a hundred and sixty-six. Ninth run in ten: thirteen thousand eight hundred. And forty-eight of the hundred and twenty never finished at all inside a budget of twenty thousand nodes.

That is a spread of more than two hundred to one within the runs that finished, and an unbounded spread once the ones that did not are counted. There is no single number that describes what this patch costs, because the cost is not a number — it is a distribution with a long tail, and the tail contains two runs in five.

The last point is worth making explicitly, because a search that fails to finish is easy to misread. Nothing about the tail is evidence that the patch is short of answers. Every finishing run produced a witness, twenty different seeds produce twenty distinct witnesses, and the set of consistent letterings is evidently large. The tail is a fact about the route, not about the destination.

The best run obeys the same law #

The four easy patches cost 0.55, 0.55, 0.56 and 0.54 nodes per panel, which the essay reads as a search doing one thing per panel. The rhombille’s best run is eighty-four nodes on a hundred and fifty-seven panels — 0.535 per panel.

That is not near the four figures; it is inside them. The largest patch, at its best, sits at the bottom of the band the other four never leave.

So all five patches obey one law and differ only in how reliably they meet it. The rhombille’s median is 1.06 nodes per panel, twice the law; its ninth decile is eighty-eight per panel, a hundred and sixty times it. The law is not broken on the fifth patch — it is achieved on the good runs and abandoned on the rest.

That is a cleaner statement of the cliff than “cost tracks size on four and not on the fifth”. Cost tracks size on all five when the search guesses well, and the fifth is the one where guessing well is not the usual outcome.

Seventy per cent of the creases are deduced #

The constant itself is worth reading, because 0.55 nodes per panel is not one decision per panel and the shortfall is the propagation doing its work.

Count in creases rather than panels, since a crease is what a node decides. The square patch has eighty-four creases and takes twenty-seven nodes; the rhombille has two hundred and eighty-two and takes eighty-four. That is 0.32 and 0.30 nodes per crease.

About seventy per cent of the creases are never chosen at all. They are forced by the vertex conditions once a neighbour is set, and the search only ever picks the remaining three in ten.

Two things follow. The first is that the propagation is doing three quarters of the work and the branching a quarter, which is why the arc test’s cheapness matters so much — it is being run at every one of the decisions, and there are far fewer of them than there are creases.

The second is that the ratio is the same on all five patches, uniform tiling or not. Whatever separates the rhombille, it is not that its conditions propagate less far: they settle the same seven creases in ten there as anywhere. The difference is entirely in what happens at the three that are left, which narrows the search for a cause to the branching and away from the constraint structure that feeds it.

What makes it different #

The rhombille is the largest of the five, and size is the first explanation to reach for and the wrong one.

Size is doing something — a hundred and fifty-seven panels is nearly twice the triangular patch’s eighty-three — but not this. If cost tracked size, the rhombille would take about ninety nodes, which is what its best run takes. The best run is where size predicts. Everything above it is something else.

The something else is what the collection has already identified as the quantity that governs these patterns: the number of independent closed chains of panels, which is the number of places a circle could sit and comes out equal to the interior vertex count. Thirty-six on the square patch, forty-five, fifty-four, sixty, and a hundred and twenty-six on the rhombille.

A hundred and twenty-six chains is not twice sixty in the relevant sense. Any subset of the chains can combine into a longer one, so the number of circuits a lettering has to avoid closing grows as two to the power of the count — and the difference between two to the sixty and two to the hundred and twenty-six is not a factor of two.

What a node is, and why the unit matters #

A number like twenty-seven nodes is only meaningful if the node is a fixed amount of work, so it is worth saying what one is.

At each node the search does the same three things. It propagates: every vertex’s list of surviving labellings is filtered against the letters decided so far, and any crease all the survivors agree about is written in. It tests the arcs: the letters decided so far orient part of a fixed graph, and the graph is swept for a directed circle. Then it picks the vertex with the fewest labellings left and sets one more crease.

The second of those is the only one whose cost grows with the pattern, and it grows linearly: a sweep over the panels and the arcs, which on the rhombille is a hundred and fifty-seven and two hundred and eighty-two. So a node on the largest patch costs about three times a node on the smallest, and the node counts across patches are comparable to within that factor.

The arc test being cheap is the whole reason it can be run at every node. Rebuilding the folded sheet to ask the same question would cost about three milliseconds — a thousand times more — and the search would be run the way the sampler is run, with the test at the end, and would not finish at all.

The two-vertex tiling #

There is a second difference and it may be the real one, though nothing here separates the two.

Four of the five tilings have vertices all alike: four squares at every point, six triangles, three hexagons, or the elongated grid’s single class. The rhombille has two kinds of vertex, and that is the whole reason it is in this collection: the matching condition that fixes how large each twist polygon must be is invisible on a tiling whose vertices are all the same, and becomes an equation on one whose vertices are not. Its hexagon’s sides sit three times further out than its triangle’s, and nothing else folds flat.

So the rhombille’s pattern has two classes of twist polygon at two sizes, joined by pleats of two different widths, and its interior vertices come in two degrees. Every other patch here is uniform.

Whether the tail comes from the chain count or from the mixture is not decided by these five measurements, and it would take a family with the counts and the uniformity varied separately to decide it. That family is constructible — the twist construction takes any tiling — and it is not built here.

There is a third candidate and it is the one the collection would have reached for first: the turn angle. It is ruled out cleanly. The twist angle moves the consistency share not at all — thirteen of a hundred and twenty at every turn from a sixth of a radian to a full one — and the same holds for the search: the four uniform patches stay in their tight bands at every angle tried, and the rhombille keeps its tail. Whatever separates the fifth patch from the other four is combinatorial rather than geometric, which is the same conclusion the rarity measurement reached by a different route.

What “hard” means, carefully #

It is worth being exact about what has and has not been shown, because hard is a word this subject uses in a technical sense a few doors down.

Deciding whether a general crease pattern folds flat is NP-hard, and that result is about a family of instances rather than about any one pattern. Nothing here bears on it. The question this search answers is not flat-foldability; it is whether an admissible lettering exists whose arcs close no circle, which is a constraint problem over a fixed graph and is not known to be hard in that sense at all.

What has been shown is narrower and is a statement about this algorithm on these patterns: the cost has a distribution with a long tail on one of the five, and the distribution is generated entirely by the order of the decisions. A different algorithm might have no tail. A cleverer choice of which crease to decide next almost certainly would have a shorter one.

That is not a disclaimer so much as a description of where the finding sits. It is an empirical fact about a search, of exactly the kind that decides how such searches are run in practice.

The shape of the tail #

A distribution with two runs in five above a cutoff and a best case two hundred times below the ninth decile has a name in the literature of search, and the shape is not peculiar to paper.

A backtracking search makes an early decision, cannot tell whether it was a good one, and pays for a bad one by exploring a subtree that contains no answer. On most runs the early decisions are fine and the search walks out. On a minority the first or second decision commits it to a region where the constraints cannot be satisfied, and the cost of discovering that is the size of the region — which on a problem with a hundred and twenty-six interacting circuits can be enormous.

That produces a distribution with most of its mass near the cheap end and a tail whose weight falls slowly, and the practical consequences are the interesting part: the mean is dominated by runs that have not happened yet, and running longer is a poor use of effort compared with running again.

The four easy patches show the other half of the picture. Their searches never make a decision they have to take back more than a handful of times, so there is no subtree to be stuck in, and the distribution is a narrow band. The difference between the two behaviours is not gradual across the five patches; it is four of one and one of the other.

Why an average would be a lie #

The temptation with a table like this is to report a mean, and a mean would be actively misleading here in a way worth naming, because it is a trap this collection could easily have fallen into.

Take the hundred and twenty rhombille runs. Forty-eight of them did not finish. If those are recorded at their budget — twenty thousand — the mean comes out near eight thousand and looks like a large but ordinary number. If they are dropped, the mean of the rest is about three thousand and looks like a moderate one. Neither number describes anything: the true value of an unfinished run is unknown and larger than twenty thousand, and averaging a known quantity with an unknown one produces an unknown quantity wearing a decimal point.

So the runs that hit the budget are recorded as unfinished rather than as their budget, and the quantities reported are the ones that survive that treatment: how many finished, the best, the middle of the finishers, and the ninth in ten. Those are order statistics and they do not need the tail’s values, only its size.

The same discipline is what makes the four easy patches’ numbers say something. Every one of a hundred and twenty runs finished, between twenty-five and thirty-six is a complete description of a distribution. It is a much stronger statement than any mean, and it is available precisely because there is no tail.

What the sampler said about the same five #

It is worth laying the two orderings side by side, because they are not the same ordering and the collection now has both.

By how often a random lettering agrees with itself, the patches run twenty-six in two hundred, five, two, none and none — square, elongated, hexagonal, triangular, rhombille, in that order, monotonically down.

By how much a search costs, they run twenty-seven, thirty-four, forty-three, forty-five and a hundred and sixty-six — the same order, but with the first four separated by a third and the last by a factor of four.

The orderings agree, and the shape does not. Consistency falls off a cliff between the elongated patch and the hexagonal — a factor of two and a half in one step — while the search cost is barely moving there. The search cost falls off its cliff one place later. Two quantities that both measure something about the same difficulty, disagreeing about where the difficulty starts.

The reconciliation is that they measure different things: one is the density of good answers in a set, and the other is how long a directed walk takes to reach one. A set can be sparse and easy to walk into, which is what the hexagonal and triangular patches are — two in two hundred, and forty-three nodes. That the two quantities come apart even further on a crumple is the clearest case, and it is a different family entirely.

Where the ladder goes next #

A cost whose spread is two hundred to one and whose worst cases never finish is not a cost to be paid patiently. It is one to be managed, and the management is simple enough to state in a sentence: stop, reseed, and start again.

What that is worth is measurable from exactly the hundred and twenty runs above, and the answer is a factor of thirty-two.

The other direction this opens is the family nobody has built. The twist construction takes any tiling, and the two candidate explanations for the tail — the chain count and the two kinds of vertex — can be separated by tilings that have one without the other. A tiling with two vertex classes and few chains, and a uniform tiling with many, would settle it. Any tiling makes a twist, so the material is there; what is missing is the work.