The route built from the gluing

The route, not the sheet found that a backtracking search’s cost on a glued sheet belongs to the pair of sheet and route, not to the sheet. Asked under eight branch orders instead of one, a cut cell’s cost barely moved while the torus over the same drawing ran from 69 nodes to 24,636. It offered an account of which routes are cheap — the ones that place first the letters whose choice propagates through an identification, because on a glued sheet those letters constrain twice — and proposed the experiment that would test it: build the route from the account, and see where it lands among the drawn ones.

The cheapest route crosses later sharpened the question. On every sheet the cheapest of eight drawn routes starts searching, rather than propagating, a period or two later than the typical one, so part of every sheet’s threshold belongs to its route. And one sheet was the opposite case: on the rhombille torus at two periods no drawn route was cheap, and “a constructed route that was would be evidence that the rhombille’s difficulty belongs to the route after all”.

This builds the route. It does settle the rhombille, and it shows that the account, as stated, was one reading of a phrase that has two.

Two ways to read “through an identification” #

A route here is the order the search takes creases in. The search’s own rule, at every node, takes a crease at the vertex with the fewest consistent letterings left, and a seed decides which letter is tried first; eight seeds give eight drawn routes. A built route keeps the seeds and changes only which crease comes next: among the creases the rule would consider, it prefers those in a chosen class, and falls back on the rule’s own preference within the class. On a cut sheet nothing is glued, both classes are empty, and a built route is the drawn route — node for node — which is the experiment’s control.

The class can be read off the glued sheet two ways, and they are not the same set.

Creases the gluing joins. A crease that runs off the right edge of the period cell continues from the left edge; the two pieces are one crease of the torus and take one letter. Its letter constrains the vertices at both ends of both pieces, which is the most literal sense of “propagates through an identification”.

Creases a loop round the torus crosses. The search’s loop test asks whether the letters force a chain of panels each above the next. On a torus such a chain can close in the cell, or it can close only after going round — and the second kind is a contradiction only if its steps round the torus add to nothing. The creases whose arcs carry a step round the torus are the ones such loops pass through, which is the sense in which a choice “propagates through” the gluing to the loop test rather than to a vertex.

On every glued sheet measured the two sets have about the same size — 24 and 25 creases on the rhombille torus, 20 and 20 on the square — and share exactly two creases. They are two different constructions from one sentence, and each is a route.

A sheet no drawn route finishes #

On the rhombille torus at two periods, none of the eight drawn routes finishes inside twenty thousand nodes. Six of the eight routes that take the joined creases first do, at 1,183, 2,743, 4,121, 11,938, 12,089 and 19,836 nodes. The routes that take the crossed creases first finish none.

The control holds exactly: on the same cell cut from the plane, where nothing is glued, both built routes cost what the drawn routes cost, run for run, from 67 nodes to one search that does not finish. And on the torus at one period, below its threshold, every route of every kind finishes in a few dozen nodes, which is propagation.

The built route does not make the rhombille torus propagate. Its cheapest finish, 1,183 nodes on a sheet of 192 creases, is about six nodes a crease, and the median of its finished searches is near forty — far above the third of a node a crease that propagation costs. What the built route does is make the sheet searchable: a search that backtracks, but backtracks over choices it can recover from, instead of one that commits early to something it spends twenty thousand nodes failing to undo.

So the question the earlier essay posed has an answer. The rhombille torus is not hard for the sheet; it is hard for the routes that were drawn. Six routes in eight, built from the gluing, settle it. The difficulty that looked like a property of the tiling — the irregular tiles, the one tiling of five whose cut sheet already had a spread — belongs mostly to the order the search took its creases in, and an order that takes the gluing’s own creases first avoids most of it.

Past the threshold, built against drawn #

The rhombille is one sheet. Every tiling has a size past which its torus stops propagating and starts searching, and the same comparison can be made at that size on each.

Across the four sheets, drawn routes finish 9 of 32 searches, routes taking the joined creases first finish 16, and routes taking the crossed creases first finish 9. The first construction is nearly twice as likely to finish as a drawn route, which is what the account predicted. The second finishes exactly as many in total — and that total hides a split, because it wins where the first loses.

Taking the joined creases first is the better construction on the rhombille, where it finishes six searches to none, and on the triangular torus at three periods, four to one. Taking the crossed creases first is the better one on the honeycomb at three periods, where it finishes five searches to the joined-first routes’ three and matches the drawn routes. On the square torus at five periods all three kinds finish three searches each. The honeycomb’s preference shows again below its threshold, in the next figure, and measured separately it holds at four periods too, where in eight searches of each kind only one crossed-first route finished at all. There is no single reading of “propagates through an identification” that is right on every tiling.

Below the threshold, a help and a harm #

Below the threshold every route is mostly propagation, and the drawn routes nearly always finish. What a built route can change there is the tail: the dearest of the eight.

On the honeycomb at two periods the dearest drawn route costs 5,306 nodes and the dearest route taking crossed creases first costs 321 — every one of the eight inside 321. On the triangular torus at two periods the dearest drawn route costs 4,477 and the dearest joined-first route 229. Those are the account working as hoped: the built route removes the tail without making the cheap searches dearer. On the square torus at four periods the drawn routes leave two searches unfinished and the crossed-first routes finish all eight.

On the elongated torus at two periods it is the other way round. Every drawn route finishes, the dearest in 638 nodes. Two of the eight joined-first routes and three of the eight crossed-first routes do not finish at all. Preferring the gluing’s creases there walks the search into exactly the kind of early commitment the drawn routes avoid. A built route is a stronger instruction than a drawn one, and a strong instruction that is wrong for the sheet costs more than a weak one.

Which decision the route changes #

A backtracking search decides two things at every node: which crease to letter next, and which letter to try first. Which choice the cost lives in found that on cut crease patterns the whole of the cost lay in the second — the letter — and that improving the first, the structural choice every search designer reaches for, made matters worse. A built route changes only the first. It keeps every seed’s letters and alters nothing but the order in which creases are decided.

On glued sheets that is the decision that matters, and the reason is where the expensive part of a search lives. The order that proves nothing exists priced a refutation at two to the power of the free choices sitting above the contradiction it ends in. A glued sheet’s characteristic contradictions involve its gluing: a loop round the torus, or a vertex whose creases meet across the cell’s edge. A route that decides the gluing’s creases late leaves dozens of free choices above those contradictions, and each wrong one costs a search of everything beneath it; a route that decides them early meets the contradictions while there is little above them to undo. The cut sheet has no such contradictions, which is why its cost lived in the letters instead and why a built route there changes nothing.

What the account got right, and what it did not #

The earlier account had the right object. On glued sheets the cost of a route depends on when it reaches the creases the gluing ties together, and a route built to reach them early is, on balance, much better than a route that reaches them whenever its rule happens to: nearly twice the finished searches past the threshold for the first construction, and a sheet settled that no drawn route could settle.

It did not have the right sentence. “The letters whose choice propagates through an identification” names two different sets of creases on every glued sheet, and they help on different tilings. Nothing measured here says why the rhombille and triangular tori want the joined creases and the honeycomb wants the crossed ones. One reading is about vertices and the other about loops, and a sheet whose dear routes fail at a vertex would want the first while a sheet whose dear routes fail by closing loops round the torus would want the second — but that is a guess with a definite test, not a finding.

Half the slack found three orders of magnitude between two measurements that looked like one, and the dial and the tiling that is not alike found the rhombille to be the one tiling of five whose difficulty a parameter could move. The rhombille is now also the tiling whose difficulty a route can remove, and the two facts are probably one: its irregular tiles are what make the order of its creases matter so much. A region with no lettering looked for the rhombille’s difficulty in its sector angles, where a corner of the parameter space has no consistent lettering at all; at the settings measured here the torus has letterings, and the difficulty was in finding one, which is a property of the search.

What eight routes of each kind cannot show #

Whether a better construction exists. Two readings of one sentence were built; a route that took the joined creases first on some tilings and the crossed ones on others, or interleaved them, or ranked creases by some third property of the gluing, might beat both everywhere. The comparison here is between two constructions and the search’s own rule, not between built routes and the best route.

Costs beyond the budget. Every search is stopped at twenty thousand nodes. A route that does not finish may finish at a hundred thousand; the counts of finished searches are counts inside a budget, and a different budget would move them, though the rhombille’s six-to-none could not move the other way.

Larger sheets. The honeycomb at four periods is the largest torus measured, and only one search of the twenty-four run on it finishes. Whether built routes keep their advantage as the cell grows, or whether every route eventually searches, is the threshold question again, one level up.

The sheets and routes measured #

The sheets are period cells of five tilings, glued into tori by joining both pairs of opposite edges, and the rhombille cell also cut from the plane as the control. A route is a branch order: the search branches on a crease at the vertex with the fewest consistent letterings left, and a built route prefers creases in its class over all others before applying that rule. The eight seeds are the same on every sheet and for every kind of route, so a built route and a drawn route with the same seed try the same first letters and differ only in which crease they decide next. Cost is nodes of the search tree until a consistent lettering is found.

The control, and four requirements #

On every cut sheet both built routes are required to cost exactly what the drawn routes cost, run for run, since with nothing glued there is nothing to build from. On the rhombille torus at two periods no drawn route may finish and at least five joined-first routes must. Past the thresholds the joined-first routes must finish more than one and a half times as many searches as the drawn ones, and the better construction must differ between tilings. Below the thresholds at least two sheets must have their dearest drawn route beaten tenfold by a built one, and at least one must have both built routes finishing fewer searches than the drawn ones. And on every glued sheet the two classes are required to differ, and on every cut sheet to be empty.

The last figure is the one the thresholds came from, and it is what made the choice of sheets here a measurement rather than a selection: each torus above was chosen at the size where its drawn routes leave propagation, not at a size where a built route happened to look good.

Still open: why each tiling wants its own construction #

The test of the guess above is a count of how each dear route fails. A drawn route that runs out of budget spends its nodes refusing letters, and each refusal is either a vertex with no consistent lettering or a loop the letters close. If the rhombille’s dear routes fail mostly at vertices and the honeycomb’s mostly by loops round the torus, the two constructions are each answering the failure their sheet has — and a route that read the failure as it went, taking joined creases after a vertex refusal and crossed creases after a loop refusal, would be a construction that adapts to its sheet. A long run shows itself early found on a cut patch that the loop refusals alone separate long runs from short, which is the same counter put to a different use.

The other direction is the elongated tiling, which the built routes made worse. It is the one sheet where every drawn route finished, and one node per panel, with the rim gone found that removing a sheet’s rim removes the letters that could not be wrong, so that what is left costs more a panel. A glued sheet’s joined creases are where its rim used to be, and a route that takes them first may be taking exactly the letters most able to be wrong first; a built route on a sheet that propagates is then an interference with propagation, and whether that is always what happens below a threshold, or particular to the elongated tiling’s mixed squares and triangles, is a measurement on the four other tilings at one period.

The habit worth carrying is about accounts that come as sentences. Before testing an explanation by building from it, check how many things it could be built into. One sentence about identifications became two constructions with two crease sets sharing two creases, and each was right somewhere; testing only the first would have confirmed it on three tilings and been puzzled by the fourth.