Search order — the series
-
Which choice the cost lives in
A backtracking search takes two decisions at every step — which thing to decide, and what to decide about it. The literature is almost entirely about the first. On these crease patterns the whole of the cost was in the second, and the structural improvement everybody reaches for first makes matters worse on fifty-two patterns out of eighty-seven.
-
The order that proves nothing exists
Twelve crease patterns with no consistent lettering at all. Proving it takes fifteen steps under one rule and half a million under another — and on three of the twelve the two rules swap places, so neither is the good one. The cost of a negative is two to the power of how many free choices sit above the contradiction.
-
What the rim was doing
One rectangle of a twist tessellation, cut out of the plane in the ordinary way, gives up a consistent lettering in forty-eight steps. Join its opposite edges so that no crease is divided and the same drawing, at the same vertices, under the same conditions, takes fifty-six thousand seven hundred and seventy-two. The edge of the paper was never the difficulty. It was the slack.
-
Pruning on proofs alone
A search that discards a branch it cannot prove wrong is not a search. Deciding whether a periodic pattern's layer relations really contradict themselves is far dearer than the disc's one-pass test, so the cheap test is asked first — it is sufficient, so it settles almost everything — and the expensive one runs only on what the cheap one rejects. Five of nine steps on a small cell, fifty thousand of fifty-seven on a large one.
-
Half the slack
Gluing one pair of a cell's edges removes half the free letters and costs almost nothing. Gluing the second pair removes the other half and costs three orders of magnitude. The letters go linearly and the search does not, and the reason is that the last free letter is worth more than all the others.
-
Which pair is glued
A cell's two cylinders have the same Euler number, the same amount of rim and the same name. On a symmetric drawing they have identical counts of letters, panels and vertices — and searching them costs twenty-four nodes one way and eighty-five the other. Half the rim is a description of the topology and not of the object.
-
Each drawing has its own threshold
Gluing a cell's edges was measured once, at one size, and found to cost three orders of magnitude — which cannot tell a threshold from a slope, nor say whether a cut sheet has one further out. Swept from one period to five on four tilings, every sheet starts at about a third of a node per free letter and every drawing leaves that behaviour at a size of its own: four periods on the square grid, three on the honeycomb, two on the triangular grid and two on the rhombille, where even the cut sheet crosses.
-
The route, not the sheet
Every cost measured for a glued sheet has been one number from one branch order, and a backtracking search's cost belongs to the pair. Asked under eight orders instead of one, a cut cell's cost barely moves — 42 to 55 nodes — while the torus over the same drawing runs from 69 to 24,636, with one order giving up entirely. The glued sheet's best order costs less than twice the cut sheet's, so most of what a single order charged to the gluing belongs to the route through it.
-
The cheapest route crosses later
A search for a consistent lettering has a threshold: below it the letters propagate and the cost is a third of a node per crease, above it the search backtracks and the cost explodes. The threshold was measured with one branch order. Measured with eight, the cheapest route never starts searching before the typical one, and on most sheets it starts a period or two later — so part of every threshold on the record belongs to the route. And the one cut sheet past its threshold, the rhombille's, spreads across nearly three orders of magnitude of cost, which moves the spread off the gluing and onto the threshold.
-
The route built from the gluing
A search for a consistent lettering of a glued sheet costs a third of a node a crease on its cheap routes and thousands on its dear ones, and an account was offered of which routes are cheap: the ones that take first the creases whose choice propagates through the gluing. That account can be turned into a route rather than tested on samples, and there are two ways to read it. Built the first way, a route finishes nearly twice as many searches past the threshold as a drawn one does, and on the rhombille torus — where none of eight drawn routes finishes inside twenty thousand nodes — six of eight built routes do, the cheapest in 1,183. So the rhombille's difficulty belongs to the route. But which reading works changes with the tiling, and on the elongated tiling, where every drawn route finishes, the built ones lose searches.
-
The torus keeps its tail
Reading why a branch failed removes the heavy tail from the search for a lettering of a cut sheet: on the rhombille drawing at two periods five of eight searches finish becomes eight of eight, and glued along one pair of edges none of eight becomes eight of eight. Glued along both, it stays at one of eight, and it stays there when every refused loop is also remembered. Two accounts of why are refuted on the way: every refusal on every sheet is a loop, so tilings do not differ by how they fail, and a torus's refusals blame no more of the stack than a cut sheet's. What separates them is the length of the proof. Undo twenty decisions from a stopped run and the proof that the letters left are already lost takes 33 nodes on a cut sheet and about 2,400 on a torus, so a jump on a torus has nothing short to read.