UniversitätsRechenZentrum

Fakultät für Mathematik und Informatik

- Introduction
- Known Solutions until 1992
- Current State of the Art
- About the implemented Algorithm
- Online Access to the Database
- Latest Calculations
- Open Conjectures
- Symmetry Remarks
- A Superficial Explanation
- Sub No-3-in-line Solutions
- Confirm the Configuration
- Distribution of Markers
- References until July 1992
- Corrections to published Data
- Summary in Tabular Form

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.

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.

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.

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/3PI*points selectable such that any three of them do not lie in a straight line.^{2})^{(1/3)}n - 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!

Therefore one
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.

*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*Acland-Hood*, 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]*Gerken*, personal communication of H. Harborth 1990, [21,23]*A. Flammenkamp*, Journal of Combinatorial Theory Series A, V.60/1992 pp. 305 - 311 [...,44,46]

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 symmetry.

Any comments or questions please to

Achim Flammenkamp

1998-03-05 17:30 UT+1