A trapped run is holding four letters

A long run shows itself early found that the search for a lettering of the rhombille patch carries a counter worth reading. A hundred and twenty runs were each stopped at node fifty and asked how often the loop test had refused them, and the runs refused sixteen times or so were nearly all long. Restarting on that count cost 387 nodes in expectation, against 483 for the best fixed cutoff.

It ended on a lead with a definite answer. The pile-up at sixteen looked like an early choice every trapped run had made, so the letters a trapped run holds should agree on a crease, and a rule about that crease would replace the restart policy with something cheaper: never take that letter on that crease first.

The measurement answers the question, and the answer is that no such crease exists. Something smaller does, and following it leads somewhere the last several essays on this search did not expect: past the restart altogether, to a change in one line of how the search backtracks, on the same seeds, which takes the tail away.

No letter can be the wrong one #

Start with why the lead fails, because the reason is a one-line argument and it would have saved the measurement.

A lettering is consistent when the mountains and valleys it assigns pass the vertex conditions and force no loop of panels each lying above the next. Turn every letter over, mountains to valleys and valleys to mountains, and the vertex conditions are unchanged, since they read how many of each and which are neighbours and treat the two letters alike. Every layer relation reverses, so a loop stays a loop and a stack with no loop stays a stack with no loop. Physically this is nothing at all: it is the same folded sheet looked at from the other side.

So for every consistent lettering with a mountain on some crease there is another with a valley on it, and a rule that forbids one letter on one crease would forbid nothing a search needs to avoid. Whatever traps a run, it is not a letter. It can only be a relation between letters, a statement of the form “these two the same and those two different”, which turning everything over leaves untouched.

The runs agree. Every one of the hundred and twenty takes the same six creases first, because the branching rule goes by which vertex has fewest options left, and the coin decides only the letter. Among the thirty loudest runs those letters split about evenly on all six, as they do among the rest. The difficulty was in the coin located the tail in the randomised letter, and that stands. The coin cannot be wrong in any one toss, though; it can only be wrong in how two tosses combine.

Four creases sort the loud runs from the rest #

Reading pairs of creases instead of single ones finds it at once. Among the thirty loudest runs, at node fifty, crease 150 and crease 152 hold different letters without exception; crease 150 agrees with crease 18 without exception; and crease 152 agrees with crease 177. Among the other ninety none of those relations is universal. Name the four creases A, B, C and D, and write what a run holds on them with mountain first, so that a run and its mirror image count as one.

The separation is complete, and this was not expected of a measurement on 120 runs. The thirty runs holding M V M V are refused fifteen to seventeen times by node fifty, and not one of the other ninety is refused more than eleven times. All eight columns are occupied, so every relation among the four letters does arise, and only one of them produces the cluster the earlier essay noticed. The sixteen is a property of those four letters, and the count was reading it from outside.

What those letters are becomes plain when the search is asked directly. Force M V M V onto A, B, C and D and search for a lettering that extends them, and none exists. Force any one of the other seven patterns and a lettering exists. Force any three of the four letters and a lettering still exists, found within about a hundred nodes when the search starts near them. Four letters out of 282 creases, none wrong alone and no three wrong together, and the sheet has no lettering that contains them. Fourteen of the sixteen ways of lettering these creases are fine, and the other two are one mistake seen from both sides.

They are not a tight group. B and D share a vertex, and A and C each stand a panel or two away, in a region at the left of the sheet that would not catch the eye on the drawing. Nothing in the picture says these four rather than some other four, which is a useful thing to know about pictures of crease patterns. The contradiction lives in the layer order, and the drawing is of the crease pattern.

Seven nodes against twenty thousand #

The refutation is the part worth looking at, because it shows the size of the thing a trapped run is failing to find.

Take the creases nearest the four first, and the proof is seven nodes long: try crease 149 both ways, try crease 179 both ways under each, and each of the four resulting letterings closes a loop of panels through six or eight creases. That is all of it, and it can be checked by hand on the drawing. Run the same question under the search’s own order, the one that branches at whichever vertex has fewest options wherever on the sheet that vertex is, and three different seeds were each still going at three hundred thousand nodes.

Seven and three hundred thousand are the same question, asked of the same sheet. The order that proves nothing exists found the cost of a negative to be two to the power of how many free choices sit above the contradiction, and this is that statement seen from a run’s position. The free choices the search’s own order places above the contradiction are all about other parts of the sheet. Every one of them is innocent. The search re-decides each of them, both ways, and meets the same four letters and the same loop at the bottom of every branch.

Every stuck run is standing on a proof #

Thirty runs with one relation is one trap, and it does not account for the others that never finish. Nineteen of the thirty never finish; the other eleven get out, having reached and changed a letter at A, B, C or D, some of them in under three hundred nodes. And another twenty-nine runs never finish while holding some other pattern on the four. So the question has to be asked of every unfinished run: when it runs out at twenty thousand nodes, is it holding letters that were already lost, or has it simply not arrived?

A run’s stack when it stops is a list of decisions, oldest first. The earliest point in that list at which the letters held have no extension can be found by testing beginnings of the list, and the test is a search with a proof at the end of it. Doing this for all 48 unfinished runs gives a definite answer.

All 48 are lost, and none has merely not arrived. Every one of them holds, between 8 and 27 decisions above where it has stopped, letters that have a proof of no lettering, and the median is 21 decisions. The proofs are short: 35 nodes at the median and 179 at the longest. The run spent twenty thousand nodes, and a proof of its situation was available in a hundredth of that. Below the mistake there are $2^{21}$ ways to settle the decisions it has made since, and the search has no way of knowing that none of them bears on the contradiction. That is the heavy tail, with nothing left over to explain.

The earlier account of the cluster said a run refused sixteen times “has made an early choice that dooms everything below it and is discovering that one branch at a time”. That is right about the mechanism and it turns out to be general. It was written about one cluster and it is true of every unfinished run on the patch, including the ones whose counts look healthy, and that second part is why the refusal policy could only ever catch some of them. Twenty-nine doomed runs do not make a noise, because what they are held by takes longer to close.

The word for this is older than the tail #

A search that keeps failing for the same reason, on branch after branch, because the decision responsible is far above the ones it is changing, has a name. It is called thrashing, and Alan Mackworth’s 1977 paper on consistency in networks of relations took the thrashing that backtracking is prone to as the thing to be explained and removed. The cure was named first recorded a long list of what this search had met second: a tail described in the 1990s, an arithmetic for restarts from 1993, a universal schedule, dynamic restart policies from 2002. All of those were answers to a question whose diagnosis was older than any of them.

And the treatment was named in the same few years. Richard Stallman and Gerald Sussman published dependency-directed backtracking in 1977, in a program that analysed circuits, in which a failure is traced to the assumptions that actually produced it and those are what get changed. John Gaschnig’s backjumping, from his work at the end of the same decade, jumps up the stack past decisions that could not have mattered. Patrick Prosser’s conflict-directed backjumping of 1993 is the form used here, in which every assignment carries the set of decisions that forced it, so that a failure can name exactly which of the decisions on the stack it depends on. In satisfiability, João Marques-Silva and Karem Sakallah’s GRASP made the same move central in 1996, and conflict analysis has been at the centre of satisfiability solving since.

Each of those is the same sentence: when a branch fails, read why, and change a decision the reason mentions. The search here had every piece of it to hand. It knew, at the moment of forcing, which vertex forced each letter. It proved at every refusal that a loop existed, on a graph from which the loop’s creases could be read in one more pass. It took neither, kept a count of how often a refusal had happened, and went back one step.

The same seeds, reading the refusal #

So the experiment is one change. Each letter carries the set of decisions behind it: a chosen letter names itself, and a forced letter names whatever forced it. A loop refusal finds a shortest loop and collects the sets of the creases on it. A decision that set does not mention is not tried again, because its other letter would meet the same loop. Everything else stays where it was: the same vertex tables, the same propagation, the same branching rule and the same coin, on the same 120 seeds.

The first figure is what happens. All 120 runs finish, where 72 did. The longest takes 462 nodes, where the longest finishing run took 17,675 and 48 did not finish at all. Half the runs take 136 nodes or fewer. On 21 seeds the two searches take the same number of nodes, because those runs never had a decision worth jumping over; the quick runs were quick for the reason they always were. What the change removes is the long part.

Then the comparison the last several essays were building towards.

The best cutoff chosen in hindsight costs 483, as stopping is cheaper than finishing first drew it, and watching the refusal count from inside the run brings that to 387. Reading the refusal costs 148 with no restart of any kind. Then the last bar: searching every whole-number cutoff for this new search and taking the best in hindsight, which is 308, saves about a tenth of one node. A restart has nothing left to do. What the hindsight was worth and a failure teaches a schedule nothing priced very carefully a schedule for a tail that need not have been there.

None of those essays was wrong. Each of them priced what it said it priced, for a search that backtracks chronologically, and the search literature did the same work on solvers of the same kind. But the shape of the argument was: here is a tail; what is the cheapest way to live with it? A rediscovery can be of the wrong result: a chain of six results, each correctly imported, can lead away from a seventh that was older than all of them, because each one’s question came from the one before it. The heavy tail arrived first in this search’s story and framed everything after. The word thrashing would have framed it differently.

Where this reaches, and where it does not #

The surprise here is how little changed, and it is worth being careful about what that does and does not show.

One patch and one family of seeds. These are the runs the earlier essays measured on the rhombille patch. The other four patches of the same construction have no tail, and on them the two searches take exactly the same number of nodes on all 120 seeds, none past 53. So on these five patches the tail and the thrashing are the same event, and that is the whole of the claim. Heavy-tailed behaviour in general search has been reported in solvers far more elaborate than this one, and the tail was named somewhere else is not contradicted: Ryan Williams, Carla Gomes and Bart Selman’s backdoors of 2003, small sets of variables that make a problem easy once set, were proposed as one account of it, and A, B, C and D with the two further creases of their proof look like a small instance of that idea. Nothing here tests that reading.

Four creases are one trap of many. M V M V is the loudest and smallest core found. The other unfinished runs hold refuted letters too, and reducing those by deleting letters one at a time gives sets of five to several dozen, which are minimal in the sense that no one letter can go but need not be the smallest available. No census of all the minimal contradictions of this sheet has been made.

A lettering is not a folded sheet in hand. Consistency here means the vertex conditions and no forced loop among layer relations of zero-thickness panels, which is the disc’s test on an idealised sheet. Every lettering the new search found was put back through the two instruments that did not find it and passed, which is the check available; that paper would actually collapse along any of them is a further question, and the drawing cannot show one.

What was checked, and how #

The control is exact. With the jumps switched off, the new search blames every decision on the stack for every refusal, which is what going back one step amounts to. On all 120 seeds, compared up to two thousand nodes, it matches the old search’s node count and outcome, which is what makes the difference in the first figure attributable to the jump and to nothing else.

A jump is safe in one direction. A decision is passed over only when the refusal did not name it, and such a refusal would recur under the decision’s other letter. A loop through a crease no vertex constrains cannot be traced to decisions, so it blames everything and falls back to the old move. On the two patterns proved earlier to have no lettering at all, it reports none.

The four creases are read, not assumed. The letters at node fifty come from re-running each seed at a budget of fifty with the coin spent exactly as the search spends it, and the figure requires that every run reading fifteen or more holds the one pattern and that no other run does.

Still open: whether a jump survives a gluing #

Everything above is a cut sheet, and the sheets that have troubled this search most are the glued ones. What the rim was doing found that joining a cell’s opposite edges takes a search from forty-eight nodes to more than fifty thousand. Whether that was thrashing too is the obvious next measurement, and a result either way would be informative: if reading refusals cures the torus then the rim was never the difficulty, and if it does not then a torus has something a cut sheet lacks, which would be the first real account of what.

The other direction is the four creases themselves. A pattern’s smallest contradictions are objects in the same sense its vertices are, and nothing collects them. Which crease patterns have a contradiction of four letters, whether their positions can be read off the tiling rather than found by search, and whether the rhombille’s irregular tiles are why it has such small ones while the other four patches have none in reach, are questions the proof above makes it possible to ask.

The habit worth carrying is about what a process discards. When a search counts its failures, look at what each failure was before counting it. The count was enough to save a fifth of the cost. The failure itself, a loop whose creases were one pass away, was enough to remove the problem, and at every refusal of every run it was left unread.