For a general overview of Langford's Problem, start with John Miller's Page http://dialectrix.com/langford.html
As a quick into, start with 1, 1, 2, 2, 3, 3
but reArrange it as 2, 3, 1, 2, 1, 3
There are now two other numbers between the pair of 2's
three other numbers between the pair of 3's
one other number between the pair of 1's
We can also reArrange 1, 1, 2, 2, 3, 3, 4, 4
as 2, 3, 4, 2, 1, 3, 1, 4
1 thru 5 will fail.
You will have to leave one or more gaps.
That is, you won't be able to pack everything into the original 2*5=10 positions.
1 thru 6 will also fail.
With 1 ... 7, and 1 ... 8 we can again find solutions.
With 1 ... 9, and 1 ... 10 we again fail.
In fact, it can be proven that you have no hope of success unless you are trying 1 ... 4N-1, or 1 ... 4N.
The proofs DO NOT say that you will succeed in finding a solution, only that you must fail with
1 ... 4N-2 or 1 ... 4N-3 Nice, tight proofs about failure, but no proof of success.
Generally, one simply has to search for solutions. See https://oeis.org/A014552
But there are "patterns", constructions, that produce solutions, one or a few of the huge number that exist.
One such construction is due to Roy O. Davies. It takes advantage of patterns like
10 8 6 4 2 . . 2 4 6 8 10
and 9 7 5 3 1 . 1 3 5 7 9
where the "." means we have to put something there, but we don't know what yet.
But we DO have each of the numbers placed twice with the correct spacing between them.
Now, look over the following pair of solutions.
For 1 ... 15, the elements 14, 15 and 7 make a sort of frame.
For 1 ... 16, it's the elements 14, 15, 16 and 7.
In both cases, the rest of the elements fit into this frame using "patterns".
14 15 7 14 7 15
12 10 8 . . . . . . . . 8 10 12 . 13 11 9 . . . . . . . . . 9 11 13
5 3 1 1 3 5 6 4 2 2 4 6
14 15 16 14 7 15 7 16
12 10 8 . . . . . . . . 8 10 12 . 13 11 9 . . . . . . . . . 9 11 13
5 3 1 1 3 5 6 4 2 2 4 6
In the Geogebra screen, use the sliders to specify N. The app will compute 4N and show the construction.
Mark and unMark the checkbox labeled "Subtract 1", and note that very little changes.
Note that there are four "patterns", each involving N-1 elements.
