Origami & Folding
what one sheet can do
Rigid folding

A search with nothing to reorder

One search on a crease pattern costs eighty steps or fifteen thousand depending on the order it takes its decisions in. The other search on the same crease pattern costs 1,188,571 steps whatever order it is given — twelve permutations of the panels, twelve identical counts. The difference between them is one line of code that neither has and one has.

Assumes Two refusals that refuse differently and Which choice the cost lives in.

19 min read 8 figures The machine is not the handLocal rules, global behaviour

This collection asks two search questions about a crease pattern and they are entirely different questions with entirely different machinery behind them.

The first is about letters: is there an assignment of mountains and valleys whose implied statements about which panel lies above which do not contradict one another? The second is about stackings: given the letters, is there an actual ordering of the panels that satisfies the two non-crossing rules, so that no panel passes through another?

The two refuse different patterns, which is the reason both exist. What is less obvious, and much sharper, is that they respond to a reordering of their own decisions in opposite ways.

Refused at one lettering is not refusedSix developable quadrilateral meshes, each with every labelling of its creases enumerated and every consistent one put to a search over orderings of its nine panels. Two of the meshes fold at no labelling whatever. Two others were refused at the labelling they were built with and fold at others.the bar is how many letterings of the mesh can have their panels stackedout of every labelling of its twelve creases, enumeratedmesh 3016 pass every vertex · 16 agree with themselves · arrived refusedmesh 5032 pass every vertex · 32 agree with themselves · arrived refusedmesh 8832 pass every vertex · 32 agree with themselves · arrived refusedmesh 11832 pass every vertex · 32 agree with themselves · arrived foldablemesh 141416 pass every vertex · 14 agree with themselves · arrived foldablemesh 19416 pass every vertex · 16 agree with themselves · arrived refusedtwo of the meshes have none at all, and two more were refused only at the lettering they came with
Fig. 1 Six quadrilateral meshes, asked both questions. The letters are consistent on all six; the ordering search refuses four of them. The bars are what the second search costs, and the first costs five or six steps on every one.

The first search: order is everything

The lettering search propagates. Writing a letter on one crease forces letters on others through the conditions at their shared vertices, those force more, and the forcing runs until it stops deciding anything. Then the search branches on a crease the propagation has left free, and the propagation runs again.

Because of that, the order the search takes its decisions in changes which parts of the sheet get settled and when — and therefore how big a subtree the search commits to before anything objects. Replacing one line’s coin toss with a constant turns a cost that ranges from eighty-six steps to fifteen thousand into a flat eighty. Branching on a different rule turns a quarter of a million steps into sixty-three, or fifteen into half a million, depending on the pattern.

Four orders of magnitude, in both directions, from nothing but the order.

The second search: order is nothing

The ordering search places panels from the bottom upward. At each height it tries each unplaced panel in turn, checks the constraints whose panels are all now placed, and either continues or backs out.

Permuting which panel is called which changes the order it tries them in, exactly as changing the branching rule changes the lettering search’s order. Twelve permutations were tried on each of seven patterns.

The node counts are identical. Not close: identical, on every permutation of every pattern, from the fold-and-cut triangle’s 1,636 to the hexagon twist’s 1,188,571.

What the coin was buyingThe number of distinct letterings returned by the same search under three orders, on one tessellation patch. A coin at every choice returns a different lettering nearly every run; a constant returns the same one every time, which is what the cheaper cost is paid for.the bar is how many DIFFERENT letterings 40 runs returneda coin at every choice2525 of 40 runs found onea constant, with the coin only on the creases no vertex constrains140 of 40 runs found onea constant at every choice140 of 40 runs found oneon the rhombille patch, 157 panels and 282 creases
Fig. 2 What the search is actually exploring, forty times over: every arrangement of the panels that survives the constraints so far, built one height at a time. Each run walks a different part of the same space and they all cost about the same.

Why one moves and the other cannot

The reason is a single structural difference and it is worth stating carefully.

The ordering search checks. At each node it asks whether the partial ordering built so far violates any constraint whose panels are all placed, and that question is about the arrangement rather than about the search. Every partial ordering that survives the checks is visited, and every one that does not is refused at the moment it is built. So the set of nodes the search visits is exactly the set of surviving partial orderings — a property of the crease pattern, computed by nobody’s choice — and permuting the labels visits the same set in a different sequence.

The lettering search propagates. At each node it deduces letters that follow from the ones already chosen, and what it can deduce depends on which letters those are. Two different orders reach different partial states, deduce different amounts and prune different subtrees, so the set of nodes visited is genuinely different from one order to the next.

Propagation is the whole of the difference. A search that only tests has a fixed tree of surviving prefixes and no order can shrink it; a search that deduces has a tree whose shape it partly determines.

The one line that separates them

It is worth putting the two searches side by side at the level of what happens at a node, because the difference is genuinely one step.

Both maintain a partial answer and extend it. Both check whether the partial answer is already impossible. Both back out when it is. The lettering search does one further thing: before choosing what to decide next, it deduces — running the vertex conditions to a fixed point and writing in every letter that follows from what is already fixed.

That step is what makes an order matter, and the mechanism is direct. Deduction consumes the freedom in the problem, and how much it consumes depends on what was fixed first. Fix a crease whose vertex is nearly determined and the deduction cascades; fix one whose vertex is wide open and it does nothing. So two orders arrive at states of different sizes, and the trees below those states are different trees.

Without deduction there are no states of different sizes. Every node is a partial ordering of a fixed length, the check on it is the same check whatever route reached it, and the tree is the same tree read in a different sequence.

The circuits a lettering orients, on the hexagonal patchThe hexagonal tessellation patch with each crease drawn heavier the more of the arc graph's 54 independent circuits it lies on, from 0 to 17. The circuits are a property of the drawing: a lettering points each arc and cannot move it.heavier means the crease lies on more independent circuits77 panels, 130 arcs, circuit rank 54; circuits run from 4 to 16 arcs
Fig. 3 The structure the first search’s deduction runs through — circuits over a patch’s panels. The second search has this structure too and cannot use it, because it never deduces anything and therefore has nothing for a structural rule to inform.
The coin's forty answers and the constant's one, on the rhombille patchNode counts for 24 runs of one lettering search on one crease pattern of 157 panels and 282 creases, ranked. Under the search's own random choice of which letter to try first the cost runs from 86 to 15872 with 7 runs unfinished; under a constant choice every run costs 80.the dot is one run's cost, ranked; the rule is the constant order1001e+31e+4nodes visited24 seeds, ranked by cost80 nodes, every seed7 unfinished at 20,000same pattern, same conditions, same test at every node — the only difference is which letter is tried first
Fig. 4 What “unpredictable” costs on the first search: twenty-four runs of one search on one pattern, ranked. The second search’s twenty-four runs would be twenty-four copies of one number.

Which is the better place to be

Neither, and the pair is worth having precisely because they trade against each other.

The ordering search’s cost is predictable. A pattern of thirteen panels costs 1,188,571 nodes and will cost that whatever anybody does, so the cost can be estimated in advance from the pattern and a budget can be set with confidence. It is also enormous, growing roughly factorially, which is why the search refuses more than eighteen panels rather than sampling and calling the result a count.

The lettering search’s cost is unpredictable and usually tiny. It runs on patterns of two hundred and eighty-two creases in eighty steps, which the ordering search could not approach — and the same search on the same pattern can cost three orders of magnitude more with one line changed, which took a great while to notice.

So one search is cheap and treacherous and the other is expensive and honest, and a collection that wants both cheapness and predictability is asking for something neither offers.

One order decides what a yes costs, the other what a no costsNodes visited by the same lettering search on three twist tessellation patches, under two rules for choosing which crease to decide next. Branching on the creases that lie on many independent circuits buys nothing when a lettering exists, and on the two patches where none exists the two rules swap places by four orders of magnitude.the bar is nodes visited, on a logarithmic scalesame search, same conditions — only the rule for choosing the next crease differs1101001e+31e+41e+5rhombille patch, turn 0.35 · a lettering exists · fewest labellings left80rhombille patch, turn 0.35 · a lettering exists · most independent circuits84rhombille, turn 0.15 · none exists · fewest labellings left511,999rhombille, turn 0.15 · none exists · most independent circuits63hexagonal, turn 0.15 · none exists · fewest labellings left15hexagonal, turn 0.15 · none exists · most independent circuits2,047on a yes the structural rule buys nothing; on a no it is worth four orders of magnitude, in whichever direction the pattern decides
Fig. 5 What “unpredictable” means on the first search: the same pattern, the same conditions, two rules for choosing what to decide next, and four orders of magnitude between them.

The expensive search is exponential, not factorial

The ordering search’s cost is described as growing roughly factorially, and its own node counts say otherwise by a wide margin — which changes what its refusal threshold means.

Three data points are given. Seven panels cost 1,636 nodes; nine cost between seven and nine thousand; thirteen cost 1,188,571.

Between nine and thirteen the count multiplies by about a hundred and fifty, over four extra panels — a factor of 3.5 per panel. Between seven and nine it is 2.2 per panel. Factorial growth over the same four panels would have multiplied by 10×11×12×1310 \times 11 \times 12 \times 13, which is seventeen thousand.

So the search is exponential at a base near three, and it is more than a hundred times slower than factorial over the measured range. The constraints are pruning hard enough to turn n!n! into something like 3.5n3.5^{n}, which is a very large saving that the description hides.

Which is where the refusal threshold comes from

That rate explains the cut-off, and it makes it look like a decision rather than a resignation.

Extrapolating from thirteen panels at 3.5 per panel: fourteen is four million, sixteen is fifty million, and eighteen is about six hundred million nodes. That is the order of a budget a build can just about contemplate and comfortably above one it can afford, which is exactly where the search refuses.

Under a factorial reading the same threshold would sit at 18!18!, six quadrillion, and the refusal would look absurdly conservative — a search declining at a point it could have reached a dozen panels earlier. Under the measured rate it sits where a budget sits.

So the eighteen is calibrated to the real growth rate, whether or not anybody worked it out, and the factorial description makes the machinery sound cruder than it is.

It also changes what a modest improvement would buy. Halving the base from 3.5 to 1.75 — which a stronger constraint might do — would move the threshold from eighteen panels to about thirty, since 1.75301.75^{30} is roughly 3.5183.5^{18}. Against a factorial the same improvement would buy two panels. The search is in the regime where a better bound is worth a dozen panels rather than one, which is a much better reason to work on it than the one the essay’s closing section gives.

The practical residue is a diagnostic, and it is one question rather than a procedure.

Does the search deduce anything? If it only generates candidates and tests them, no ordering heuristic will help, because the set of survivors is fixed and heuristics only reorder a fixed set. Effort belongs somewhere else entirely — a stronger constraint, a symmetry to quotient by, a bound to prune with.

If it deduces, ordering is worth attention and is worth measuring separately for its two halves, because the two choices a search makes are not the same choice and the one that gets the attention is not reliably the one that is costing.

That question is cheap to answer and it went unasked here for a long time, during which considerable effort went into a distribution that a search-without-propagation could not have produced.

Why the expensive search is not simply improved

The obvious response to a search whose cost cannot be reordered is to give it a deduction step, and it is worth saying why that is a substantial piece of work rather than an afternoon’s.

The lettering search’s deduction is cheap because the vertex conditions are local: everything they say concerns the creases meeting at one point, so propagating them is a sweep over vertices with a small table at each. The ordering search’s constraints are not local in that sense. A taco constraint involves four panels that may lie anywhere on the sheet, a tortilla constraint involves three, and deducing from them means reasoning about relations between panels rather than about a neighbourhood.

That is not impossible — it is the difference between testing a partial order and maintaining one, and there is a well-developed way to do it — but it changes the search’s character entirely and it would forfeit the one virtue it currently has. A predictable factorial cost is a bad cost that can be planned around; an unpredictable one that is usually much better and occasionally worse is what the other search offers, and this collection now has a good deal of evidence about how easy that is to misread.

Trying mountain first and trying valley first cost the sameNode counts for the same lettering search run twice on each of 5 crease patterns, once trying a mountain at every choice and once trying a valley. Every point lies on the diagonal, which is what a symmetry of the problem looks like when it is measured rather than assumed.each point is one patch, searched twice002020404060608080square · 26elongated · 32hexagonal · 39triangular · 39rhombille · 80nodes, mountain firstnodes, valley firstthe dashed line is y = x, and nothing has been fitted to anything
Fig. 6 What the ordering search is counting, and why improving it does not help: trying the panels one way round costs exactly what trying them the other way costs, on every patch. There is no order of exploration that is cheaper, because there is nothing to reorder.

The meshes, which show both at once

The six quadrilateral meshes are the cleanest available demonstration because both searches run on the same six objects.

Their letters are consistent on all six, found in five or six steps apiece with no backtracking anywhere — the first search’s ordinary behaviour on a small regular pattern. Four of the six have no stacking at all, and establishing that costs between seven and nine thousand nodes each.

Three orders of magnitude between the two questions on identical inputs, with the cheap one answering a necessary condition and the expensive one answering the real question. That gap is the reason the cheap test is worth running first, and the reason its answer must never be reported as the answer.

A strategy against the absence of the problem it solvesThe expected total cost of cutting a lettering search off after a given number of nodes and starting again with a new seed, against the cost of not randomising the search at all. The curve is a correct answer about a distribution the search itself produced.the curve is stop-and-restart; the rule is a constant letter order1001e+31e+41001e+31e+4563 at a cutoff of 10080 nodes, deterministic, nothing to restartexpected nodes in totalcutoff, in nodes
Fig. 7 What the expensive search returns, priced as a decision: whether to abandon a run at a budget and begin again. On a pattern whose orderings are all alike there is nothing a second attempt could find that the first did not, which is what makes the reordering free and the search dear.

What a person does instead

Neither search resembles what a folder does, and the second one is the more instructive mismatch.

Asked which panel goes on top, a folder does not enumerate arrangements. They fold the sheet and look. The paper performs the search by being paper — every constraint the ordering search tests is enforced automatically, because material cannot pass through material — and the answer arrives in the time it takes to collapse the model.

That is why the enormous cost of the ordering search is not a statement about folding being hard. It is a statement about deciding without folding being hard, which is a different task that only exists because a crease pattern can be drawn and reasoned about before any paper is committed. The first thing about layers is the observation that a folder learns the answer without ever framing the question.

What the search buys is the ability to answer for a pattern that has not been folded and possibly cannot be — including, crucially, the ability to return no, which a sheet of paper cannot do convincingly. A folder who fails to fold something has learned that they failed.

The refusal the letters can see, and the one only a search canSix developable quadrilateral meshes, each asked twice whether its panels can be stacked: once by reading the arcs its letters force, and once by searching every ordering. The letters agree with themselves on all six; the search refuses four of them.the bar is the nodes the ordering search visitedthe letters are consistent on every one of these, so the one-pass test says nothing about any of themmesh 37,4739 panels · 7,473 nodes · no order existsmesh 58,0079 panels · 8,007 nodes · no order existsmesh 89,3469 panels · 9,346 nodes · no order existsmesh 111,0159 panels · 1,015 nodes · an order existsmesh 141449 panels · 144 nodes · an order existsmesh 199,0629 panels · 9,062 nodes · no order existsa red bar is a pattern with no folded state, found only by visiting every ordering it might have had
Fig. 8 The two refusals side by side. One is read off the crease list in a single pass; the other requires visiting every ordering the pattern might have had, and only the second can say that nothing works.

Which theorem was checked, and how

The order-invariance is asserted rather than observed. Each pattern’s panels are relabelled by twelve permutations, the ordering search is run on each, and the assertion requires that the node count and the number of orderings found be identical across all twelve. Either differing would mean the search was reading something it should not — a panel’s index rather than its geometry — which is the defect this check exists to catch.

The lettering results are checked as they are everywhere here: every witness written back onto its pattern and put past the four conditions at every interior vertex and a folded sheet rebuilt from scratch, and every exhaustion agreed by more than one order.

What the picture cannot show

The permutations. A figure showing twelve identical numbers is a figure showing one number, and the interesting content is the absence of variation rather than any value — which is why the claim is carried by an assertion rather than by a chart.

Nor does order-invariance mean the ordering search cannot be improved. It means it cannot be improved by reordering. Adding propagation to it — deducing that one panel must lie above another from constraints already fixed, rather than merely testing — would change everything, including making its cost order-dependent. That is a considerable piece of work, it is the obvious next thing, and it would trade the search’s predictability for the other search’s unpredictability rather than getting both.

And seven patterns is seven. The invariance follows from the search’s structure and would be surprising to find violated, which is why it is written as an assertion over whatever patterns are to hand rather than as a survey.

What it would take to be wrong

The claim that an exhaustive test-only search cannot be reordered is close to a tautology once stated, and it is worth naming the two ways the measurement could nonetheless have come out otherwise — because both are real defects that this check is really looking for.

The search could read an index. If any constraint were expressed in terms of a panel’s number rather than its geometry — a comparison, a sort, a tie broken by index — then relabelling would change what the search accepts, and the node counts would diverge. That is an easy mistake to make and a hard one to notice, since the search would still return correct-looking answers on every pattern anybody tried.

The search could prune inconsistently. It refuses a partial ordering the moment a constraint whose panels are all placed is violated, and “all placed” depends on the order the panels were placed in. So a constraint could in principle be checked earlier under one labelling than another, refusing a prefix sooner and visiting fewer nodes. The counts being identical says that every prefix is refused by some constraint at the same depth regardless — which is a stronger and less obvious statement than the tautology, and it is the part worth having measured.

Twelve permutations on seven patterns is not a proof of either, and it is enough that a systematic version of either defect would have shown.

The reading that transfers

Outside this subject the distinction has a short name and a long history: generate-and-test against constraint propagation, and the difference between them is exactly the difference measured here.

A generate-and-test search enumerates candidates and rejects the bad ones. Its cost is the number of candidates that survive whatever partial checking it can do, that number is a property of the problem, and no reordering touches it. Everything that helps such a search is a stronger check — something that rejects more, earlier.

A propagating search deduces consequences and then chooses. Its cost depends on which consequences it has drawn when it chooses, so ordering is decisive, and the two orders it chooses in are not one knob but two.

The diagnostic that follows is a single question and it takes a minute: does anything in this search deduce? Answering no means ordering heuristics are wasted effort. Answering yes means they are worth attention and worth measuring in both halves. It is a cheap question and this collection went a long way without asking it.

Where the ladder goes next

There is a third way to ask about a folded state, and it has no discrete choices at all: a motion has no letters to choose, where the fold angles are continuous and solved rather than searched — which removes the ordering question entirely and introduces a different failure in its place.

Where this goes next

the bar is the nodes the ordering search visitedthe letters are consistent on every one of these, so the one-pass test says nothing about any of themmesh 37,4739 panels · 7,473 nodes · no order existsmesh 58,0079 panels · 8,007 nodes · no order existsmesh 89,3469 panels · 9,346 nodes · no order existsmesh 111,0159 panels · 1,015 nodes · an order existsmesh 141449 panels · 144 nodes · an order existsmesh 199,0629 panels · 9,062 nodes · no order existsa red bar is a pattern with no folded state, found only by visiting every ordering it might have had Two refusals that refuse differently Four of the six developable quadrilateral meshes this collection solves have no ordering of their nine panels — they must pass through themselves, and a search over every ordering proves it. On all four, the letters agree with themselves perfectly. The linear proof and the exponential search are not a fast test and a slow one: they answer different questions, and neither contains the other. heavier means the crease lies on more independent circuits157 panels, 282 arcs, circuit rank 126; circuits run from 4 to 26 arcs 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 bar is how many letterings of the mesh can have their panels stackedout of every labelling of its twelve creases, enumeratedmesh 3016 pass every vertex · 16 agree with themselves · arrived refusedmesh 5032 pass every vertex · 32 agree with themselves · arrived refusedmesh 8832 pass every vertex · 32 agree with themselves · arrived refusedmesh 11832 pass every vertex · 32 agree with themselves · arrived foldablemesh 141416 pass every vertex · 14 agree with themselves · arrived foldablemesh 19416 pass every vertex · 16 agree with themselves · arrived refusedtwo of the meshes have none at all, and two more were refused only at the lettering they came with Refused at one lettering Four of six quadrilateral meshes here have no arrangement of their nine panels — established by searching every ordering, at the labelling each mesh arrived with. Enumerate every labelling instead and two of the four fold perfectly well at a different one. What was reported as a fact about four meshes is a fact about two meshes and two labellings.

What this makes readable

Essays that name this one as a prerequisite.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

BacktrackingConstraint propagationExhaustive searchLayer orderingNon-crossing conditionQuadrilateral meshSearchSearch cost