Langford Oddity

I discovered this when trying to generate just the first solution for all n's less than 200 in May-June 1994. The program proceeded very quickly, but then hit a wall at 36. Wondering why, I chose to count the number of "erasures" done as a measure of the work getting there. (This tells how many times the algorithm has to backtrack in the search tree).

I had the program stop if it did not find a solution after 100K erasures so I could go on to the next number and come back to the stuborn ones later. After obtaining the partial results, I tried some fairly long runs for 47, 48, and 51 without reaching their first solutions.

I have scanned all n's upto 119 for any that take fewer than 1,000,000,000 (one billion) operations (erasures). The results are as follows. "G+" means that more than a giga-operation is still needed to obtain the first solution. I am currently revisiting each number with G+ in hopes of defining those values.

 n ops ("ops" are erasures done getting to first solution via algorithm)
-- ---
 3 0
 4 1
 7 9
 8 24
11 551
12 145
15 118
16 477
19 357
20 935
23 304
24 2,772
27 13,592
28 13,622
31 8
32 8 !
35 8 !!
36 45,611,934
39 3,661,017,408
40 43
..
43 328
44 328 !
..
47 G+  > 94 G-ops.
48 G+  > 22 G-ops.
..
51 G+  > 63 G-ops
52 3,298
..
55 7,374
56 G+  > 38 G-ops
..
59 G+  > 35 G-ops
60 G+
..
63 4,178
64 4,178
..
67 89,772
68 G+
..
71 G+
72 426,607
..
75 324,326
76 324,326
..
79 G+
80 G+
..
83 1,118,220
84 1,118,220
..
87 427,758
88 G+
..
91 G+
92 G+
..
95 23,147,636
96 23,147,636 ! ---------------------
..
 ..
 99 G+
100 G+
...
103 G+
104 518,229,284
...
107 435,334,954
108 G+

111 G+
112 G+

115 G+
116 G+

119 G+

I know that everything beyond here upto 200 takes more than 100,000 from a previous run.

Questions

Why do 36, 39 and 47, et. al. take so many operations to reach their first solution?
Why do 31/32/35 and 40 take so few?
Why do 31/32/35, 43/44, 63/64, 75/76, 83/84, 95/96, ... take the same number of operations!? (What is going on here!?)

Discussion

That a particular n (say 36) takes more to get to the first solution, does not imply that the total number of operations to enumerate all of that n won't be in line with other n's. I.e. many solutions may follow rapidly algorithmically after the first solution is reached. I need to investigate this aspect!

Whenever I look at the state-file (progress) of the program that is trying to fit 47 pairs, I see all the pairs in except for the 3's, 2's, and 1's (and sometimes 4's). So there must be something about 47 that does not leave any openings for these smaller numbers. Odd indeed!

Back to John Miller's Langford Page

Created By: miller@lclark.edu
Updated: 3-May-97