The cheapest route crosses later

Each drawing has its own threshold swept the search for a consistent lettering across sizes and found each drawing’s point of change. Below it a search assigns a letter, propagates, and almost never undoes anything, at about a third of a node per free crease; above it the search backtracks and the cost climbs by orders of magnitude. Gluing a cell’s edges into a torus moves the threshold closer, and one tiling, the rhombille, crossed at two periods without being glued at all.

The route, not the sheet then showed that every one of those costs was a single draw. Run with eight branch orders instead of one, the square grid’s four-period cut sheet cost 42 to 55 nodes whichever order was used, and the torus over the same drawing cost 69 to 24,636. The cheapest route through the torus cost less than twice the cut sheet’s, so most of what a single order had charged to the gluing belonged to the route. The essay named two experiments it did not run: the same eight orders across the whole size sweep, to find the threshold of the best route as against that of a typical one; and the rhombille’s two-period cut sheet, because a cut sheet whose cost varied with the order would be a new thing entirely.

Both have now been run.

What a threshold is, measured two ways #

A search that never backtracks spends a fixed share of a node on each letter it assigns: it chooses, propagates, and the choice is never undone. On every sheet here that share is about a third of a node per free crease at the smallest size — 9 nodes for 32 creases on the square grid’s two-period torus, 20 for 60 on the rhombille’s one-period cut cell. A route that costs more than a whole node per crease is doing something propagation does not: it is guessing, failing and returning. So one node per free crease is a line between the two regimes, and a sheet has crossed its threshold, for a given route, at the first size where that route costs more than it.

Eight branch orders give eight routes, and the question is where the cheapest of them crosses against where the middle one does. The middle one is what a single fixed order would typically report, and it is the threshold every earlier essay measured. The cheapest is as close as eight samples get to what the sheet itself demands.

The cheapest route never crosses first #

On every sheet the cheapest of the eight crosses at the same size as the middle one or later.

On the square grid’s torus the middle route crosses at four periods — 1,169 and 2,463 nodes for 128 creases — and the cheapest crosses at five, where it costs 325 nodes for 200 creases. At four periods the cheapest costs 69, which is 0.54 of a node per crease: still propagating, on a sheet the middle route is already searching.

On the triangular grid’s torus and the honeycomb’s, the middle route crosses at two periods and the cheapest at three and four respectively. The honeycomb’s cheapest route costs 70 nodes for 216 creases at three periods — a third of a node per crease, as if nothing had happened — while three of its eight routes run out of budget there. On the elongated triangular tiling’s torus the middle route crosses at two and the cheapest has not crossed by three.

The rhombille’s torus is the exception that goes the other way: the middle and the cheapest cross together, at two periods, where none of the eight finishes. On that sheet there is no easy route to find.

So the gap between the typical route’s threshold and the cheapest route’s runs from nothing to two periods or more, and it depends on the drawing. A threshold measured with one order is a threshold of that order, and on the honeycomb the difference is two whole sizes of sheet over which the difficulty was the route’s.

The sweep drawn with one order is the picture every earlier reading was taken from, and it is worth seeing beside the eight-order version: the lines it draws are single draws from the distributions the first figure summarises, and where a line bends upward depends on which draw it is.

A cut sheet with a spread #

The second experiment turned up the stronger result.

Every other cut sheet behaves as the square grid’s did. The square grid, the triangular grid, the honeycomb and the elongated tiling, at two, three and four periods, give eight routes that agree to within a factor of 1.3, and every one costs about a third of a node per crease. That is what a sheet below its threshold does: propagation settles it, and propagation does not care about order.

The rhombille’s cut sheet at two periods costs anything from 67 nodes to 13,834, and one of the eight routes runs out of its budget entirely. Its cheapest route, 67 nodes for 216 creases, is a third of a node per crease — no backtracking at all — and its dearest finishing route is two hundred times that. The 13,834 that each drawing has its own threshold reported for this sheet, and read as the rhombille crossing without being glued, is one of the eight: the dearest that finished.

At three periods the rhombille’s cut sheet has seven of eight routes out of budget and one that finishes at 7,172 nodes, fifteen per crease. By then even the cheapest route is searching.

What the spread is the signature of #

The route, not the sheet found the cut sheet’s cost a point and the glued sheet’s a band, and read the band as what gluing does to a sheet. The rhombille’s cut sheet makes that reading impossible: it is cut, and its band is as wide as any glued sheet’s.

What it shares with the glued sheets is that it is past its threshold. Every sheet whose middle route is searching has a wide band of costs across routes, glued or cut; every sheet whose middle route is propagating has a narrow one. Gluing is one way past the threshold — it removes the rim, which is where propagation starts cheaply — and the rhombille’s drawing is another, since its interior is hard enough that a rim of the usual size does not keep it under.

The earlier result survives with its cause moved. On the square grid at four periods the torus is past its threshold and the cut sheet is not, so one has a band and the other a point; the gluing is what put the torus past, and the band is what being past looks like. The spread belongs to the threshold, and gluing belongs to the list of things that move a sheet across it.

Why the cheapest route can stay below #

A route crosses when the letters it takes first stop determining the ones after them. A cheap route is one whose early choices propagate far, so that most of the sheet is settled before any choice can be wrong; a dear one takes letters whose consequences are local, fills the sheet with independent guesses, and finds the contradiction between them late.

That makes the gap between the thresholds a measure of how much of a sheet’s difficulty is choosing well. On the honeycomb’s torus the right first letters settle the three-period sheet with no backtracking at all, and three random orders in eight never find an answer inside the budget; the sheet is easy for a searcher who knows where to start and hard for one who does not. On the rhombille’s torus no order of eight is cheap, and the difficulty belongs to the sheet.

Half the slack found the last free letter worth more than all the others, and which choice the cost lives in separated the two decisions a search makes — which letter, and which value. The thresholds here are the first measurement of the first decision across sizes: the order in which letters are taken moves a sheet’s threshold by up to two periods, and on the sheets where it does, the difficulty a single order reports is mostly its own.

The record, re-read #

The thresholds on the record were each read off one route, the one a fixed seed happened to take, and the sweep says where each of those numbers sat among the eight.

The honeycomb’s two-period torus was reported at 95 nodes for its 96 creases — right on the line, which is why it looked like the size at which the honeycomb starts to cross. Its eight routes run from 30 to 5,306. The fixed seed’s route was near the bottom of the distribution; the middle of it is three times dearer and the dearest fifty-five times, and the sheet is already past its threshold for any route but a lucky one.

The rhombille’s two-period cut sheet was reported at 13,834 — the dearest of the eight that finished. The same sheet’s cheapest route costs 67, a third of a node per crease. Read at one seed, it looked like the one cut sheet that crosses; read at eight, it is the one cut sheet that crosses for most routes and not for all, which is the typical threshold and not the cheapest one.

The square grid’s four-period torus was reported at 1,169, which is the fourth of eight: a middle route, and a fair report of where a typical search stands. Its cheapest costs 69.

So the single-seed numbers were neither systematically high nor systematically low. They were draws, some near the bottom of a wide distribution and one near the top, and a sweep read from them put the thresholds wherever the draws fell. The threshold of the typical route is the one the record was trying to measure, and a single draw measures it only on sheets narrow enough that every draw is typical — which are exactly the sheets below their thresholds, where there was nothing to measure.

Why restarts work here, and where #

A search whose cost varies this much across routes is one a practitioner does not run once. The route, not the sheet measured what restarting buys: run several routes in turn, stop each at a cutoff, and keep the first that finishes, so that the cost is set by the lower end of the distribution rather than its middle. It turned 1,800 nodes into 69 on the square grid’s torus.

The sweep says where that trick applies. Below a sheet’s threshold restarting buys nothing, because every route costs the same; past it, restarting buys the whole gap between the middle route and the cheapest, and the gap is largest on the sheets where the cheapest route crosses latest — the honeycomb’s torus, the elongated tiling’s. On the rhombille’s torus, where the cheapest route crosses with the middle one, restarting buys little, because there is no cheap route among eight to restart into.

That is the pattern the study of backtracking search has described for combinatorial problems in general: runtimes whose distributions have heavy tails, where randomising the order and restarting early cuts the expected cost by orders of magnitude. Carla Gomes, Bart Selman and Henry Kautz made it a standard technique in the late 1990s. What the sweep adds for these sheets is where the heavy tail begins — at the typical route’s threshold — and how long the cheap lower end lasts beyond it, which is the gap between the two thresholds and is a property of the drawing.

What eight orders cannot say #

The cheapest of eight is not the cheapest. Eight random orders sample the space of routes; a better route than any of them may exist on every sheet, and where the cheapest of eight crosses is an upper bound on where the best route crosses. The gaps above are therefore lower bounds on how much of each threshold belongs to the route.

The budget decides where a route “does not finish”. Every route here is given ten thousand nodes on the six-sheet figure and twenty thousand on the cut-sheet figure; a route out of budget might finish at a hundred thousand, and the middle route’s cost is read as out of budget when more than half of the eight run out. The crossings are robust to that, since a route that needs more than ten thousand nodes on a few hundred creases is searching by any standard.

And one node per crease is a line, not a law. It separates a third of a node, which every sheet shows below its threshold, from the tens and hundreds above it, and nothing measured sits near it for long; a different line between the two would move no crossing.

The sheets and routes measured #

The sheets are period cells of five tilings, glued into tori — both pairs of opposite edges joined, the case which pair is glued separated from the two cylinders — or cut from the plane, at every size the search reaches: the square grid from two periods to five, the triangular grid and the rhombille from one to three, the honeycomb from one to four, the elongated tiling from one to three.

A route is a branch order: the search always branches at the vertex with the fewest labellings left, and a seeded stream breaks ties and chooses which letter to try first. Eight seeds give eight routes, the same eight on every sheet.

Cost is nodes of the search tree until a consistent lettering is found, divided by the number of free creases, so that sheets of different sizes can be read on one scale.

How the measurements were checked #

The cheapest route is required never to cross before the middle one on any sheet, with at least one sheet on which it crosses two periods later and one on which the two cross together — so a sweep in which route made no difference, or made every difference, would stop the figure rather than draw it. Every cut sheet other than the rhombille’s is required to settle within a factor of 1.6 under all eight routes with none out of budget, and the rhombille’s cut sheet is required to spread by more than fifty or lose routes to the budget.

Still open: the route built rather than drawn #

The measurement has made the question the route, not the sheet left sharper. If the cheapest of eight random routes stays below the threshold for two periods longer than a typical one, a route built from the sheet’s structure might stay below it longer still. That essay proposed the construction — take first the letters whose choice propagates through an identification of the glued sheet — and the honeycomb’s torus at three and four periods is now the place to test it: a sheet where some routes are free and most are expensive, and a size at which none of eight random routes finishes.

The rhombille’s torus is the opposite test. No random route of eight is cheap on it at two periods, and a constructed route that was would be evidence that the rhombille’s difficulty belongs to the route after all; one that was not would put it on the sheet, where a region with no lettering looked for it in the sector angles.

Sideways from here, the result belongs beside every search threshold on the record, and beside the populations a population nobody chose assembled for measurements that need many objects as well as many draws. What the rim was doing measured the rim’s work at one size and one order; a rim is where cheap routes start, so the rim’s contribution and the route’s are two readings of one quantity, and the sweep above is the first that can separate them.

The habit worth carrying is about thresholds in algorithms. A threshold measured with one method is a property of the pair; before reading it as a property of the problem, find where the best method crosses. On these sheets the answer moved by up to two sizes, and on the one sheet it did not move at all — which is the sheet whose difficulty can now be called its own.