A row the route cannot leave

The helix chooses the lattice finds that the double helix’s pitch places crossovers at whole bases on a honeycomb lattice and never on a square one. A design drawn on squares asks the helix to wind a little more loosely than it does, and the mismatch accumulates into a twist that has to be corrected base by base. So the lattice the molecule prefers is the honeycomb.

Every earlier routing result was computed on the other one. Two ceilings finds that solid blocks route easily and branching shapes do not, and that a strand’s length is what stops a block while the routing is what stops a plus. On squares a rectangle never has trouble: every helix reaches every neighbour, and a boustrophedon along the rows always works.

On the honeycomb a helix has three neighbours instead of four, and in a block drawn as rows it reaches the row above at only every second position. That is a different graph, and the question is whether a rectangle of it can still be threaded in one pass.

The honeycomb, drawn as rows #

A honeycomb lattice looks unlike a grid, and the useful way to draw it for this question is the way design software draws it. Put the helices in rows. Every helix touches the helix on its left and the one on its right. Beyond that, each touches exactly one helix in an adjacent row — the one above or the one below — and the choice alternates along the row, like the courses of a brick wall.

That drawing is the honeycomb exactly: every helix has three neighbours, a third of a turn apart in the real bundle, and the brick courses are what those three directions look like when the rows are straightened. It keeps a row a row, so a block of w helices by h means the same thing on both lattices and the two censuses compare like with like.

What changes is the vertical traffic. On squares a route can climb from any helix to the row above; on the honeycomb it can climb from only half the helices in a row and descend from the other half. A row is a corridor with doors on alternate sides.

Twenty of eighty #

The first figure is the census: every block up to ten wide and eight tall, on each lattice, put through an exhaustive search for a route.

On the square lattice all eighty route. On the honeycomb twenty do not, and they fall into three groups with three different reasons.

Six are disconnected. A block one helix wide and three or more tall is a column, and in brick courses a column’s helices alternate between reaching up and reaching down, so the column comes apart into pairs. No strand crosses a gap, and these are not routing failures so much as blocks that are not one piece.

Twelve are odd in both directions. Every block of three, five, seven or nine helices wide by three, five or seven tall has no route. The colour count — which refuses a shape whose two colours differ by more than one — passes all twelve, because an odd block has one more of one colour than the other, which a route starting and ending on the majority colour allows.

Two are narrow and even. Blocks three wide by six tall and three wide by eight tall have no route either, for a different reason taken up below.

The twelve are the finding. They are solid rectangles, the shape that never gives the square lattice any trouble, and they fail on the honeycomb at every size tried.

The row that closes on itself #

The reason fits along one edge of the block, and the second figure draws it.

Take a block odd in both directions and look at its top row. In brick courses the top row’s helices alternate between reaching up and reaching down, and with an odd height the helices at even positions along the top row are the ones that reach up — out of the block, to nothing. So those helices have no neighbour off the row. The two corners are both at even positions, because the width is odd, and each has only the one helix beside it: they have a single neighbour each. The even positions between them have two, the helices on either side.

A route has to visit every helix, and a helix with a single neighbour can only be where the route starts or ends. So the route’s two ends are the two top corners. A helix with exactly two neighbours has to be passed through using both of them. So every even position along the top row forces the route to run from its left neighbour to its right neighbour.

Now look at the odd positions between. Each is already used by the even helices on both sides of it — the route arrives from one and leaves to the other — so it has no connection left for its door to the row below. The whole top row is forced into a single run from one corner to the other, and that run has both of the route’s ends in it. The route has finished having visited w helices out of w·h.

The argument does not depend on the block’s size, only on its width and height both being odd, and the census finds every such block refused.

It is also worth seeing how little of the block the argument looks at. Forty-two of the seven-by-seven block’s forty-nine helices play no part in it. Their neighbours, their colours and the routes that might run among them are irrelevant, because the row has already used up both of the route’s ends before any of them is reached. That is the property local is not global warns is rare in this subject: a local observation that settles a global question outright, rather than merely ruling out some of the candidates. It is a proof in the sense a proof in one pass is one: a chain of forced steps, each local, ending in a contradiction.

Three by three is also a cut #

The smallest odd block fails for the same reason and, separately, for a second one that the plus’s failure on squares already made familiar.

In a three-by-three honeycomb block, the middle helix of the top row is the only one on that row with a door down. Remove it and the block falls into three pieces: the two top corners, each alone, and everything below. A route passes through any helix at most once and can serve at most two pieces by passing through it, so a helix whose removal leaves three pieces is a helix no route can manage — which is the cut condition, met by a single cell.

The two tests agree on the three-by-three and part company above it. A five-by-five block has no single helix whose removal leaves three pieces, so the cut condition with one cell passes it, and the row argument still refuses it.

Odd one way is enough to escape #

The census has a clean boundary, and the boundary is the parity of the width.

A block odd in height but even in width routes. With an even width the top row’s last helix is at an odd position, so it reaches down rather than up, and the corner at that end has two neighbours instead of one. The route has only one forced end on the top row, the row no longer closes on itself, and a route can leave it through the far corner’s door.

Blocks even in height have their top row’s doors on the other positions, the corners reach down, and nothing on that row is forced. They route, with the two narrow exceptions.

The two narrow blocks #

Three by six and three by eight have no route, and the row argument does not reach them: their heights are even, so nothing on the top or bottom row is forced to be an end.

What refuses them is the cut condition with two cells. Remove the middle column’s third and fourth helices, counting from the bottom, of a three-by-six block and it falls into four pieces, more than two cells and two ends can serve. That is the general form of the condition two ceilings derived — a set of s cells leaving more than s + 1 pieces rules a route out — met here by a pair.

So every one of the twenty failures in the census is caught by a cheap test: disconnection, the colour count, the cut condition with one or two cells, or the forced row. None of them needed the exhaustive search to be refused, although the search confirms each one.

What the square catalogue already knew #

The square lattice’s catalogue had its own failures, and setting them beside the honeycomb’s shows what changed and what did not.

On squares, every failure was a shape with a branch point — a plus, a T, a comb — and every one was caught either by the colour count or by removing a single cell and counting the pieces. Solid shapes never failed, because on squares a solid shape has no helix whose neighbours are all in one direction. The lesson drawn there was to count the branch points.

On the honeycomb that lesson is not enough. A solid rectangle has no branch points and still fails, because its edge is a row of helices with low degree, and low degree in a line behaves like a branch point spread out. The general statement that survives both lattices is the one parity is not enough makes about crease patterns and even is not enough makes about colourings: a cheap count is necessary, a cut is necessary, and neither is the answer — but on a sparser graph the cheap tests have more to do, and they do more of it.

That is a point about lattices rather than about any shape. A lattice with fewer neighbours per site makes every shape drawn on it closer to the edge of routability, because more of its sites sit where a route’s choices are forced. The honeycomb’s three neighbours against the square’s four is the whole of the difference in the census.

Euler’s count, and why it usually fails #

A test that counts neighbours has a famous ancestor, and the comparison says why the honeycomb’s row argument is unusual.

In 1736 Euler settled whether a walk could cross each of Königsberg’s bridges exactly once by counting, at each piece of land, how many bridges met it. A walk passes through a piece of land using bridges in pairs, so only the walk’s two ends can have an odd count, and a city with more than two odd pieces has no such walk. The count at each vertex decides the whole question, and it is both necessary and sufficient.

A route through every helix is the other problem — every vertex once rather than every edge once — and for it no local count is sufficient. Deciding whether a graph has such a route is hard in general, which is why every result about it here is either a necessary condition or a search.

The honeycomb row is a case where a local count does decide it. The count is Euler’s kind of count, applied to the forced consequences of degree one and degree two, and on odd-by-odd blocks it is enough to settle the answer without a search. It works because the brick courses make a whole row’s degrees small at once, which the square lattice never does, and which is exactly the property that makes the honeycomb harder to route.

What the census cannot show #

The census is over rectangular blocks, and real bundles are rarely rectangles drawn in brick courses.

A honeycomb bundle’s cross-section is usually a compact hexagon-like shape rather than a rectangle, and a rectangle drawn in brick courses corresponds in the real bundle to a parallelogram of helices. The row argument applies to any shape with a straight edge of that kind; whether a design’s cross-section has one depends on the design and is not in the census.

Nor can the census show a multi-strand design. Everything here assumes one scaffold strand visiting every helix once. A design with two scaffolds, or one that leaves a helix unvisited and fills it with short strands, is asking a different question, and the twelve odd blocks may all be buildable that way.

The multi-strand escape is the same move a designer makes when a molecule refuses a polygon: the obstruction is real, and the response is to change the question rather than to answer it.

And a route that exists is not a route that folds well. The search reports the first route it finds, with no attention to where its crossovers fall, and where a helix can cross to its neighbour is a constraint on every step that the graph does not carry.

The lattice the census assumes #

A helix’s neighbours are the honeycomb’s three, in brick courses: left, right, and one of up or down, alternating. A different embedding of the same honeycomb — courses running the other way — would put the forced row on a different edge and change which blocks fail.

Every helix is visited exactly once by one strand. That is the single-scaffold design the whole routing question is about.

And a route is a path in the graph, with nothing else asked of it. The strand’s length is not charged here; the census is a routing census, and the ceiling from the strand’s length is a separate division.

How the census was checked #

Both lattices are searched with the same exhaustive search, which never consults the colouring, over every block from one by one to ten by eight — a hundred and sixty searches.

Every square-lattice block is required to route, which is the control: a search that failed on a solid rectangle of squares would be a search to distrust.

Every odd-by-odd honeycomb block from three by three up is required to pass the colour count and have no route, so the finding is observed across twelve blocks rather than argued from one.

The forced row is checked on the block it is drawn for. In the five-by-five figure the top row’s helices without a neighbour off the row are counted, the two corners are confirmed to have a single neighbour each, and the search is required to agree that no route exists while the colours balance.

Still open: the smallest shape every cheap test passes #

Two ceilings observed that the colour count and the cut condition together caught every unroutable shape in its catalogue, and said that a shape passing both with no route must exist, because deciding a route is hard, and that finding the smallest one would be a better use of an exhaustive search.

The honeycomb census does not find it either. Every one of its twenty failures falls to disconnection, the colour count, the cut condition with one or two cells, or the forced row. The shape both lattices are still missing is one that all of those pass and no route reaches, and the honeycomb, with its sparser rows, is the more promising place to look: its graphs have more helices of degree two, and forced chains of them are exactly where local tests run out of things to say.

The search that would find it is the kind of search that proves nothing exists: exhaustive, expensive, and informative in exact proportion to how cleverly the shapes it is pointed at were chosen. Blocks were not a clever choice; they were the obvious one, and the honeycomb’s forced rows mean the obvious choice is already handled by a count.

The second continuation is the ceiling. A hundred and thirteen helices is the strand’s limit on either lattice; on the honeycomb the largest blocks under it that route are the even-by-even and mixed ones, and the ceiling census of families — rows, blocks, branching shapes — is worth redoing to see which of the two limits each family meets first.

The habit worth carrying is about lattices generally. Before trusting a result computed on a convenient grid, ask which moves the grid allows that the real object does not. On squares a rectangle has no corridors; on the honeycomb its edge is one, and a result about rectangles changed sign.