Which choice the cost lives in

Every backtracking search takes two decisions at every node and they are not the same kind of decision at all.

The first is a variable choice: of everything still undecided, which to decide next. The second is a value choice: having picked something, what to try for it first. Both are free — any choice of either yields a correct search — and both change the cost, sometimes enormously.

Almost all the attention goes to the first. That is where the named heuristics live, it is where a problem’s structure most obviously enters, and it is the one a search’s author will have thought about. On the crease patterns here it turned out to be the wrong half.

What each choice can do, in principle #

The two decisions have different jobs, and the difference is easiest to see by asking what a perfect version of each would achieve.

A perfect value choice never guesses wrong. It walks straight from the empty lettering to a complete consistent one, deciding each crease correctly the first time, and the search costs one node per decision with no backtracking whatever. That is only available when a solution exists; a perfect value choice on a pattern with no lettering saves nothing at all, because there is no correct answer to guess.

A perfect variable choice never wastes a subtree. It picks, at every node, something that will be contradicted immediately if the current commitments are doomed — so a doomed region is abandoned at once instead of being explored, which is the whole economics of a refusal that fires early. That helps most when there is nothing to find, and helps a search that is going to succeed only by shortening the wrong turns it takes on the way.

So the two are not competing improvements to one thing. They are aimed at opposite outcomes, and a search that is going to succeed needs the value order while a search that is going to fail needs the variable order.

There is an asymmetry hidden in that pairing which is worth pulling out before any measurement. A value choice is only ever wrong about a decision that had a right answer, so it can be judged against the solution. A variable choice has no right answer to be judged against — any order is complete — and its quality is entirely a statement about the shape of the tree it produces. That is why the variable choice attracts theory and the value choice attracts shrugs, and it is also why the value choice is the one that quietly goes unexamined.

The standard variable rule, and the structural one #

The search here already uses the standard variable rule: branch at the vertex with the fewest labellings still available. It is the oldest heuristic in the subject and the reasoning is sound, and it is the same rule the construction that draws these patterns uses to find their letters in the first place — a vertex with two surviving labellings is nearly decided, so deciding it is nearly free of guesswork, and a contradiction surfaces close to the decision that caused it.

The structural alternative comes from what a contradiction actually is here. A lettering is inconsistent when the arcs it forces close a circle, and a circle has to run round a circuit of the panel graph. So the creases that lie on many independent circuits are the creases most likely to be involved in any contradiction the pattern has, and branching on those first should surface contradictions earlier.

The circuits are cheap to find. A spanning tree of the arc graph leaves out one edge per independent circuit, each of which closes exactly one circuit with the tree path between its ends, and counting how many of those pass through each crease is one pass over the tree. On the rhombille patch that is a hundred and twenty-six circuits over two hundred and eighty-two creases, computed in a few milliseconds.

Both rules are defensible and both have the same shape of argument behind them: surface the contradiction early. They disagree about where a contradiction is likely to be. The standard rule says it is near whatever is most constrained; the structural rule says it is near whatever the circuits run through. On a problem whose constraints are local and whose contradictions are global, the second sounds like the better bet, and a crease pattern is exactly such a problem — the vertex conditions are local and the circle they cannot see is not.

What the structural rule costs #

It costs more. Not on one patch — on most of them.

Over the eighty-seven patches of the uniform grid that have a consistent lettering, branching on the circuits is never cheaper than the standard rule and is worse on fifty-two. The worst case is the triangular patch, where a search that costs at most fifty-one steps under the standard rule costs two thousand three hundred and ninety-four under the structural one — a factor of forty-seven, paid for reading the pattern’s own structure.

That is not a small effect and it is not noise. It reproduces on every seed and on every patch size, and it is in the direction nobody expects.

Why the better-informed rule loses #

The reason is the paragraph above about what each choice is for.

A pattern that has a lettering has one that the propagation is quite good at walking toward, provided the search keeps deciding creases whose letters are nearly forced. The fewest-labellings rule does exactly that: it decides the least free thing available, so most of its decisions are not really guesses and the propagation does the rest.

Branching on circuit participation ignores how free a crease is. A crease on many circuits may have both letters wide open, and choosing it is a genuine two-way guess taken early, before the propagation has narrowed anything. The search then commits to a large region on the strength of a coin-flip-shaped decision, and the standard rule’s whole virtue — that its decisions are nearly forced — has been given away in exchange for information that only pays if the answer is no.

There is a second cost and it is subtler. The fewest-labellings rule is adaptive: what it picks depends on what has already been decided, so it follows the propagation around the sheet. Circuit participation is computed once from the drawing and never changes, so the structural rule is a fixed order, and a fixed order cannot notice that the region it is about to enter has already been settled.

A useful way to see it: the fewest-labellings rule is not really choosing a variable at all. It is choosing the variable the propagation has already nearly chosen, which makes it a way of following the deduction rather than steering it. The structural rule steers, and steering is only valuable when the deduction is going nowhere. On these patterns the deduction goes almost everywhere — the search decides a hundred and fifty panels’ worth of letters from a few dozen genuine decisions — so steering it is interference.

That reading also predicts where the structural rule would win, and the prediction turns out to be right. It wins exactly where the deduction has nothing to follow, which is a pattern with no consistent lettering at all: there the propagation never converges on anything and the search is genuinely guessing, so the guesses may as well be aimed. That case is a separate essay because it does not behave as a smaller version of this one.

Fifty-two to nothing #

The comparison’s numbers deserve one line of statistics, because “never cheaper and worse on fifty-two” is the sort of result that could still be a run of luck and here is not.

Of the eighty-seven patches, thirty-five are ties and fifty-two are decisive. All fifty-two go the same way.

Under the null hypothesis that the two rules are equally good — that each decisive comparison is a coin toss — the chance of fifty-two heads is $2^{-52}$, about one in four and a half thousand million million. Nothing about the sweep’s design needs defending against that.

What the ties say #

The thirty-five ties are not noise either, and reading them says why the two rules can agree so often on patterns where one is catastrophically worse.

A tie means the two orders cost the same, which happens when the search barely branches at all — the propagation settles nearly every crease and the few that remain are settled in an order that does not matter. Forty per cent of the patches are in that regime, and it is the same regime the cost-per-panel constant describes: about seven creases in ten are deduced rather than decided.

So the population splits into patches where there is nothing for a variable rule to do and patches where there is something and the structural rule does it badly. There is no third group.

Which forecloses the hybrid #

That has a consequence worth stating, because the natural response to “usually worse” is to use both.

A portfolio — run the standard rule and the structural rule and take whichever finishes first — is worth something only if there is some instance where the second wins. On these eighty-seven there is none. The structural rule’s expected value is not merely negative; it has no upside at all on this population, so no combination, weighting or switching rule can extract value from it on patterns that have a lettering.

That is a stronger negative than a mean comparison would give, and it is the reason the essay can recommend leaving the variable rule alone rather than recommending a mixture. A rule that never wins is not a rule to keep for the cases where it might.

The qualification is the one the essay makes elsewhere and is worth repeating here: on patterns that have a lettering. Where there is nothing to find the same rule is worth four orders of magnitude, and the sign of that four is decided by the pattern rather than by the rule.

The measurement that would have been misleading #

Had the structural rule been tried on one patch, the answer could easily have come out the other way. On the square patch it is a wash — twenty-five to twenty-seven steps either way — and on the rhombille under a randomised value order it looked, for a while, mildly promising.

What settles it is the grid: eighty-seven patterns with a lettering, swept over tiling, turn angle and pleat width rather than chosen. Fifty-two losses, thirty-five ties, no wins. A single-patch comparison here would have been a coin toss dressed as a result, and this is the same failure the collection has recorded before about populations assembled from whatever was to hand.

It is also the failure the collection’s own instrument made in an earlier round of this work. Two hundred draws produced two noughts, one of which was a genuine absence and one of which was a sampling accident, and nothing in the sampler could tell them apart. A comparison between two heuristics on one instance is the same object at a smaller scale: the answer it gives is a fact about which instance was reached for, and the only repair is a population somebody has to declare in advance.

Where the cost really was #

With the variable rule left alone, the value rule is the whole story on these patterns. Replacing the search’s coin with a constant removes the rhombille patch’s tail entirely: eighty steps on every seed against a median of two hundred and fifty and a worst run of fifteen thousand eight hundred and seventy-two.

So the accounting for these patterns is stark. The variable choice: no improvement available, and a plausible one available that costs a factor of forty-seven. The value choice: three orders of magnitude, from a change that consists of deleting a coin toss.

There is one more thing worth noticing about that asymmetry, because it is the reverse of the usual advice. A search that has a heavy-tailed cost distribution is normally taken as evidence that the instance is hard, and the standard responses — restarts, portfolios, randomisation — all treat the distribution as given. Here the distribution was not given. It was produced by the search, in the half of the search nobody had looked at, and every response that took it as given was answering a question about the instrument.

What generalises and what does not #

The narrow finding is about crease patterns and is safe: on this family, with this propagation, the value order dominates.

The wide version — value ordering matters more than variable ordering — is not supported and is probably false in general. What the measurement here really shows is something about the propagation: these vertex conditions are strong enough that the standard variable rule is already near-perfect, which leaves nothing for a better variable rule to win and everything for a value rule that avoids the few genuine guesses. On a problem whose constraints propagate weakly the balance would go the other way, and the literature this borrows from is largely about such problems.

The transferable statement is smaller and more useful: measure both choices separately before improving either. The one that will be improved is not reliably the one that is costing, and a search’s author is systematically more likely to have thought about the wrong one — because the variable choice is where the interesting structure is, and interesting structure is not the same thing as expensive structure.

The other half of the transferable statement is about where to look for the coin. A value choice does not always announce itself as a coin toss. It can be a default that was never thought about — the first element of a list, the smaller of two integers, whatever the enumeration happens to produce first — and a default is a constant, which by the argument here is fine. The dangerous case is the one that looks responsible: a value choice randomised deliberately, for a reason that has nothing to do with cost, by somebody who has correctly noticed that determinism loses something. That is what happened here, the reason was good, and the price was three orders of magnitude in the worst case.

Which theorem was checked, and how #

None of the above changes what the search decides. Every arrangement measured here returns a lettering that passes the four conditions at every interior vertex and forces no circle in a folded sheet rebuilt from scratch, and every arrangement that exhausts its tree without finding one agrees with every other arrangement that exhausts — which is what makes a completed exhaustion a proof rather than a report. The orders differ in cost and never in verdict, which is checked across the whole grid rather than assumed — an ordering heuristic that changed an answer would be a defect of the most serious kind, since it would mean the search was not exploring what it claims to.

What a folder gets out of it #

Nothing directly, and that is worth saying rather than hiding, because this collection’s rule is that the paper corroborates and never carries.

A folder handed the rhombille patch and asked to work out its letters does not run a backtracking search. They look at a vertex, see what the sectors force, mark it, move to a neighbour, and keep going — which is the propagation, done by hand, and it settles most of the sheet exactly as it settles most of the search. Where the propagation stops, a folder guesses, and if the guess is bad they discover it two vertices later and rub something out.

What a folder does not do is guess badly a hundred times in a row and unwind a quarter of the sheet each time. They carry context: a sense of which way the pleats are running, which the search does not have and which is doing the same job a good value order does. So the finding has a hand version after all, and it is the ordinary one — the difference between somebody who has folded a tessellation before and somebody who has not is not that the first knows more theorems. It is that the first guesses right.

Where the ladder goes next #

The variable choice has not finished. It buys nothing on a pattern with a lettering, and on a pattern with none it is worth four orders of magnitude — in whichever direction the pattern decides, which is what makes it a measurement rather than a recommendation. And the coin the value order removed was buying something after all, which the count of distinct witnesses prices.