Origami & Folding
what one sheet can do
Concept

Backtracking — where it appears

A search that extends a partial answer, and takes a decision back the moment what it has built becomes impossible. It decides which thing to fix next and what to fix it to, and both choices are free: the answer never changes with them and the cost can change by four orders of magnitude.

Named by 7 essays across 4 fields — each of them below, with the objects they name alongside it.

the dot is one run's cost, ranked; the rule is the constant order1001e+31e+4nodes visited40 seeds, ranked by cost80 nodes, every seed15 unfinished at 20,000same pattern, same conditions, same test at every node — the only difference is which letter is tried first

The difficulty was in the coin

One tessellation patch, one search, one test at every node — and a cost that runs from eighty-six steps to fifteen thousand depending on nothing but the starting seed. The heavy tail is real, it was measured carefully, and it was made by a single line of the search that nobody had thought of as a choice at all.

flat-folding · Forced order 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.

complexity · Search order each cell is one patch, searched to a verdictgreen: a lettering exists · magenta: none exists, by exhaustion0.150.250.350.50.70.91.11.3turn angle, in radianssquare2626262626262626elongated1515323231313232hexagonal1515394545464545triangular1515393939373737the number in a cell is the nodes the search visited; 6 of 32 patches have no lettering at all

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.

complexity · Search order 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

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.

rigid · Self-contact what each sheet costs, per panel — a square twistcut out ×10.5565 nodes on 9 panels · 12 lettersglued across ×10.6674 nodes on 6 panels · 10 lettersglued along ×10.6674 nodes on 6 panels · 10 lettersglued both ways ×10.7503 nodes on 4 panels · 8 letterscut out ×20.52013 nodes on 25 panels · 40 lettersglued across ×20.55011 nodes on 20 panels · 36 lettersglued along ×20.55011 nodes on 20 panels · 36 lettersglued both ways ×20.5639 nodes on 16 panels · 32 letterscut out ×30.61230 nodes on 49 panels · 84 lettersglued across ×32.02485 nodes on 42 panels · 78 lettersglued along ×30.57124 nodes on 42 panels · 78 lettersglued both ways ×317.361625 nodes on 36 panels · 72 lettersthe letters go down as the rim goes and the cost per panel goes up

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.

complexity · Search order what happens to the tail when a refusal is readthe most recent decision is changedthe most recent decision a refusal names is changed2340306090120the runs, each search's own sorted from quickest to longestnodes, log₁₀first search: 48 of 120 unfinished at 20,000 · second: longest run 462 nodes

A trapped run is holding four letters

Thirty of the hundred and twenty searches for a lettering of the rhombille patch are refused sixteen times in their first fifty nodes, and the proposal was to find the crease that traps them. No crease can: turning every letter over turns a folded state upside down, so no single letter is ever wrong. What the thirty share is a relation among four creases, mountain, valley, mountain, valley, and the proof that it has no lettering takes seven nodes. The runs cannot find that proof, because they change their most recent decision whether or not it had anything to do with the refusal. Change instead the most recent decision the refusal names, an idea from the 1970s, and the tail is gone: all 120 finish, the longest in 462 nodes, at an average of 148 against 387 for the best restart policy, and no restart helps at all.

history · Rediscovery searches that finish inside 5,000 nodes, of 8 on each sheetchanges the most recent decisionchanges the most recent one a refusal names101001,0005,000the rhombille tiling, 2×2, cut5 → 8the rhombille tiling, 2×2, cylinder0 → 8the rhombille tiling, 2×2, torus0 → 1the honeycomb, 3×3, cylinder7 → 7the honeycomb, 3×3, torus4 → 4the square grid, 4×4, cylinder8 → 8the square grid, 4×4, torus5 → 5the triangular grid, 3×3, torus1 → 1nodes to a lettering, on a logarithmic scale; the column on the right counts finished 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.

complexity · Search order

Named alongside it

The objects these essays reach for when they reach for this one.

Search costConstraint propagationSearchAssignmentCertificateCombinatorial explosionExhaustive searchGluingPatchBoundaryCrease assignmentCycle space

All concepts