Planar Langford pairings: P(2,31) and other notes
A message from Rory Molinari to me, John Miller on 2/19/2018
Thank you so much for your wonderful pages on Langford's problem. I came across the problem in Knuth's volume 4A. I'm also fascinated by DLX, Knuth's dancing links method for Algorithm X. I implemented DLX to understand it better (and for fun) and planar Langford pairings are an obvious problem to try it on.
I have performed a calculation that may be useful to your website and have some comments about a question you ask in your Langford's Problem, Remixed paper.
To test my implementation I calculated P(2,n) for n ≤ 28. I got the same numbers as Knuth and Dimitrov. (This was a test of my code, not theirs.)
I also calculated
P(2,31) = 5 724 640
in about 105 hours. I have confidence in my code because it gives correct results for n ≤ 28. But this value for P(2,31) should of course be regarded as tentative.
The run time for DLX on this problem appears to be close to O(2.5n), so P(2, 32) would likely take me 11 days or so. My poor laptop, which is my work machine, is not ready for such a challenge, so for now P(2,31) is as far as I can go.
I also confirmed the
quads result of Saito/Hayaska and Noble:
L(4,24) = 3
in about 3 1/2 hours. Run time is around O(4.1n); L(4, 27) lies out of reach for me at the moment.
End Run Planar Solutions
In your Langford's Problem, Remixed paper you ask for any examples of planar solutions that
do an end run:
Any example...? Is this a dumb statement?
The answers are 'Yes!' and 'No!' There is already such an arrangement for n = 4. Consider the unique Langford pairing for n = 4:
2 3 4 2 1 3 1 4
As we know, this is not planar in Knuth's sense. But consider joining lines that for 1, 2, 3, 4 go above, below,
around the end, and above, respectively. (3 runs around.)
It is not hard to represent such pairings in an exact cover problem. This allowed me to calculate the following numbers for planar solutions in which the
joining lines are allowed to do an end run. (I've called this sequence Q(2,n). I'm sure there is a better name.)
Q(2,3) = 1
Q(2,4) = 1
Q(2,7) = 6
Q(2,8) = 24
Q(2,11) = 139
Q(2,12) = 289
Q(2,15) = 2414
Q(2,16) = 4455
In OEIS.org format: 0,0,1,1,0,0,6,24,0,0,139,289,0,0,2414,4455
The branching factor in the search tree for this problem is quite high and, for now, Q(2,19) is out of reach for me. Run time is about O(4.3n) and I estimate Q(2,19) would take about 2.5 days on my laptop.
3. Further Notes
We can think of Knuth-planar solutions as follows. Take an array of numbers giving a valid Langford pairing and attach sheets of paper edgewise to the top and bottom of the array. Then the pairing is planar just when we draw non-crossing lines that join each number pair. The fact that we have two separate pieces of paper is why we can't do an end run.
For pairings that we are allowed to join
around the end we instead think of placing the Langford array in the middle of a single, large sheet of paper. Now we have more freedom in placing our lines (but, of course, the Langford array itself is
impermeable: the joining lines can't go between or
over the numbers).
- a join line is a line joining the occurrences of a given number.
- a looping join line (or just
looping join) is such a line that goes
around the end of the array.
These lines aren't allowed in Knuth's formulation.
- starting & ending — a looping join starts at the array position from which it goes up.
From there it goes
around the side of the array and ends where it joins the array from below.
We make the following observations. This is all rather hand-wavy, but I believe the logic is valid.
1. Consider two looping joins, J1 and J2. The start positions of these joins must be sorted in the same sense as their end positions. In other words, if the start of J1 is to the left of the start of J2, then the end J1 is to the left of the end of J2. Otherwise the lines would cross. Thus for any two looping joins, one is unambiguously to the left of the other.
2. Suppose there is more than one looping line in a planar pairing. If the j-th such line, reading from the left, loops around the left side of the array, then so do all the looping lines to its left. And if the k-th such line loops to the right then so do all the looping lines to its right. Otherwise lines would cross.
3. The leftmost right-looping line can be redrawn to loop to the left: we just need to draw it
big enough. We can imagine
picking up the loop (like a rope) and flipping it over to the other side.
4. So, without loss of generality we can assume all looping joins loop to the left.
5. No looping join line is needed for placements that use the first or last positions in the array. Such a line is degenerate and reduces immediately to a line
Points (4) and (5) let us reduce the size of the search tree.
These are the assumptions under which I calculated the numbers Q(2,n), above.
I can think of several other ways to generalize Knuth's planar solutions. Recall that we can think of these as using two sheets of paper, each joined edgewise to the Langford array.
A. Join the two sheets of paper at their edges parallel to the Langford array so we can get from above the array to below
around the back. (The setup would look like a cylinder on which Langford array is an end-to-end
B. Join each sheet to itself by the left and right edges. Now there are still separate sheets, but each one is a cylinder. There are no looping joins, but a joining line above the array, say, can go to the left and
reappear over on the right, rather like the avatar in certain old-school video games, like Pacman.
C. Join more than two sheets edgewise to the array.
D. Join the pieces of paper in different ways, such as with a half twist so the cylinder becomes a Mobius band. Or place the Langford array on other topological surfaces, such as a torus.
E. Consider what
planar might mean for Langford triples. I don't think we can ever simply join the three occurrences with a
join line. Such a join line for the larger entries in the array would be too constraining. Maybe we have enough flexibility if we join the (first, second) and (second, third) occurrences with independent join lines.
(Comments on A-C above follow.)
(A) is equivalent to the looping-joins case. This wasn't obvious to me at first, but it is not hard to see. Consider a solution with looping joins. As we have seen, all the looping joins loop to the left. Take the sheet of paper and puncture it at a point inside the leftmost looping join. Now stretch out the puncture until the piece of paper is a cylinder that is joined edgewise to the top and bottom of the Langford array. (This is the same operation that shows that any graph that can be drawn without crossed edges on a sphere is planar.)
(B) adds nothing to Knuth's formulation. Consider the
top most joining line that goes left and reappears at the right, Pacman-style. We can imagine cutting this line in the middle, flipping over each half, and rejoining the halves to make a normal, Knuth-style joining line. This process can be repeated until all of the Pacman joining lines have been converted.
(C) is Dimitrov's extension to higher
dimensions. I have not done any calculations here.
I have not explored (D) or (E).
Additional Info on Q-planar solutions, 3-11-2018
As we know, there are no Knuth-planar sequences for n=7, but 4 when we allow end runs. Here is one:
7 4 1 5 1 6 4 3 7 5 2 3 6 2
The unique set of joining lines (up to reflection through the axis of the array) puts the lines for 1, 2, 4, and 7 above the line, for 3 and 6 below the line, and for 5 around the end.
Of the 24 loop-planar solutions for n=8,
- 4 need no loop (end-run) joins. These are the Knuth-planar solutions.
- 5 require a single loop join
- 4 require two loop joins
- 6 require three
- 4 require four
- 1 requires five!
This is the one that requires five looping joins:
4 5 6 7 8 4 1 5 1 6 3 7 2 8 3 2
The joins for 1 and 2 go above, 4 goes below, and the rest go around the end. (Without loss of generality we can put all the looping joins around the left end of the array.)
This solution for n=12 requires 8 looping joins! Joins for 1, 2, and 5 go above, 6 goes below, and the rest loop. According to my software, 7 looping joins do not suffice.
6 7 8 9 10 11 12 6 5 7 1 8 1 9 5 10 4 11 3 12 2 4 3 2
Rory Molinari, March 11, 2017
Langford's Problem Home Page: