Fakultät für Mathematik und Informatik
The No-Three-in-Line Problem
The no-three-in-line problem is a geometric arrange problem. Let
a n × n grid be given in the Euclidean plane
for any natural number n .
The task is to mark as many of the intersection points of the n2 grid points as possible under the condition that
no three of them lie in a straight line.
One can obviously mark at most 2n points.
The problem of finding for which n this upper bound is reached is known
as the no-three-in-line problem, introduced by Dudeney 1917.
A closely related question is: How many points can maximally be marked under this
restriction? P. Erdös has shown that
(1-eps)n points can be placed in a given n × n grid for all sufficient large n.
Hall, Jackson, Sudbery, and Wild made the substantial improvement to (3/2-eps)n in 1975. This is the best known asymptotic lower bound.
But Guy and Kelly used a probabilitic argument to support their conjecture
that for large grids the limit does not reach 2n -- the main conjecture.
Until march 1992 I had computed for small values of n such no-three-in-line configurations.
The last class I counted was for n=23 with one diagonal-reflection symmetry. This was the only
missing number in my 1992 JCT publication.
All those old results are summarized in this table. To get an impression of the increasing number of examined cases have a look at the counted vertices in the recursive total tree searchi which is subdivided in the symmetry classes.
Look for a short
explanation of symmetry classes and their conditions.
The whole old data is availible in coded form via
anonymous ftp, but this old format which uses a nonalphanumeric alphabet is no longer recommanded.
Better you have a look to both, old and new, data as a collection of many files or as a list of coded configurations (1.6MB).
To decypher this code use this C-program.
For those who haven't access to a C-compiler:
Each line represents a configuration and each character in it a marker position, except the first one, which denotes the symmetry class. The positions are coded from left to right and from top to bottom in each configuration. They are numbered
by the alphabet 0,1,2,...,9,A,B,C...,Z,a,b,...,z only in their column positions.
For example here are all now known configurations with dia2- and full-symmetry.
Also you can see this as a 44KB picture of 33+3 configurations.
My program nothree needs about 4 n^4 + O(n^2) bytes storage and was
first implemented in july 1988.
Its last release was of november 1991 and consists
of about 600 lines of C sourcecode.
Also an overview of the number of configurations is given with this hopefully up-to-date table.
The used method to find these solutions is mainly a sophisticated branch and bound algorithm.
A new version was just in april 1996
implemented. Aside the fact that computers nowadays seem to be by a factor 15-20 quicker, the
refined algorithm itself gives a speedup of 1.5 - 8 depending on the examined symmetry class. It is very important to traverse the tree of the possible configurations in a proper chosen order. And this depends stronly of the symmetry class.
Furthermore with a simple trick, the restriction of n <= 64 (due to the internal data structure) could be
risen to n <= 90 without any runtime or memory increase. Currently I can check n = 72 for configurations with full symmetry in the same cputime as those for n = 60 with the old algorithm used 1991.
Since 7th June 1996 a new format for the coded configurations is in use: Now each configuration is lead in by a
symmetry-class character of the list (. : / - o c x + *) which indicates the symmetry (iden rot2 dia1 ort1 rot4 near dia2 ort2 full) respectively.
Further, the marked positions are numbered by the alphabet 0,1,2,...,9,A,B,C...,Z,a,b,...,z in their column position.
And a code word must be terminated by a newline or space or tab. As long as no configuration with n > 62 is known the more limited alphabet size doesn't matter in opposite to the old one (n > 96 would have caused problems).
- Finding configurations for larger n
- Settling the Main Conjecture of No-Three-in-Line
- Main Conjecture (<= 1967)
- There are only finite many different configurations.
- If n tends to infinity, there are only (2/3PI2)(1/3)n
points selectable such that any three of them do not lie in a straight line.
- Conjecture I (<= 1952)
- There are exactly 3 configurations having the full symmetry of the grid.
- Conjecture II (<= 1968)
- Each configuration having ort2 symmetry has the full symmetry of the grid.
- Conjecture III (<= 1991)
- There are exactly 5 configurations having reflection symmetry in the mid-perpendiculars.
- Conjecture IV (<= 1996)
- There are about 34 configurations having reflection symmetry in the main-diagonal and side-diagonal.
Conjecture III was disproved in June 1996 by the discovery of a further configuration having reflection symmetry!
To understand the relative number of solutions in the classes ort1, rot2, dia1 or the
classes ort2, rot4, dia2 notice that in the orthogonal symmetry class ort1, resp. ort2, two independent
selected points force typically the blockade of
n points for 2 of 6, respectively for 8 of 28, straight lines together with their 2, resp. 6, symmetry points.
For the diagonal reflection classes dia1 and dia2 two independent selected points force typically the blockade of n/2 points ... .
And in the rotation symmetry classes rot? two independent selected points force typically the blockade of about C log(n).
The effect of blockade of the remainding 4 of 6, respectively 20 of 28, straight lines seem roughly independent of the regarded symmetry class.
should expect most different configurations for given n in the rotational symmetry classes but least different configurations in those with mid-perpendicular symmetry. For a precise analysis of the asymmetric case, see the paper of
Guy and Kelly 1968. Their idea can be applied to a special symmetry class to
get probabilistic estimations for the number of different configurations. The
relation of the numbers for different symmetry class but fixed n
should be at least the same as the counted ones for the generatable configurations.
Here are some remarks about symmetry conditions/effects in no-three-in-line configurations.
Due to a correspondence from John Selfridge, I checked the collected configurations whether
they contain a no-3-in-line solution for smaller n than the given one. Besides the
3 known "diagonal extentions" for
o2423670617014535 , :3458148A130A7902692567 , :372845190A460A19562837
the only subsolutions I found is the 2x2 solution. Almost all of these configurations belongs to symmetry class rot2 or rot4.
Only 5 examples for n=12, 13, 14, are assymmetric and one with n=15 has reflection symmetry at its long diagonal. But there are more assymmetric for n >= 15.
Those configurations having 2x2 blocks in class rot4 have the only block at their
center, except the 2 configurations o2323676701014545 and o9OGHGHAM6M06OP34BFBTEQKL12128JALRSRS893F0IEIPQ45NT7N7JCDCD5K. There are centerblock configurations in this symmetry class for n=2,10,14,22,28,30,32,...,42,44 and
probably for more n >= 46.
- H.E. Dudeney,
"Amusements in Mathematics", Nelson, Edinburgh 1917, pp. 94, 222
- K.F. Roth,
Journal London Math. Society V.26 / 1951, pp. 204
- R.K. Guy,
Bulletin Malayan Math. Society (1952-1953), E22
Bulletin Malayan Math. Society (1952-1953), E82
- P.A. Kelly,
Master's Thesis, University of Calgary, 1967
- R.K. Guy and P.A. Kelly,
Canadian Mathematical Bulletin V.11 / 1968, pp. 527-531
- M.A. Adena, D.A. Holton and P.A. Kelly,
Combinatorial Mathematics: Proceedings of the Second Australian Conference
Lecture Notes in Mathematics, V.403 / 1974, pp 6-17.
- R.R. Hall, T.H. Jackson, A. Sudberry and K. Wild,
Journal of Combinatorial Theory Series A, V.18/1975 pp. 336 - 341 [<=10]
- D. Craggs and R. Hughes-Jones,
Journal of Combinatorial Theory Series A, V.20/1976 pp. 363 - 364 [11,12]
- M. Gardner,
Scientific American V236 / March 1977, pp. 139 - 140 [13-16]
- T. Kløve,
Journal of Combinatorial Theory Series A, V.24/1978 pp. 126 - 127 [14,16]
- T. Kløve,
Journal of Combinatorial Theory Series A, V.26/1979 pp. 82 - 83 [18,20]
- D.B. Anderson,
Journal of Combinatorial Theory Series A, V.27/1979 pp. 365 - 366 [22,24,26]
- H. Harborth, P. Oertel and T. Prellberg,
Discrete Mathematic V73/1988 pp. 89-90 [17,19]
personal communication of H. Harborth 1990, [21,23]
- A. Flammenkamp,
Journal of Combinatorial Theory Series A, V.60/1992 pp. 305 - 311 [...,44,46]
In the 1992 published enumeration table in JCT wrong numbers
were given in column o for n >= 30. A program bug causes some missed solutions in symmetry class rot4, which were discovered now by a recomputation.
The correct numbers are 92 instead of 62 for n = 30 and 101 in place of 99 for
n = 32.
Due to my unconcentration the value for n=20 in column : is a misscount. The correct
value is 675 instead of 693, the value of all configuration with at least rot2
Any comments or questions please to my current Email-address
Back to my HomePage
1998-03-05 17:30 UT+1