UniversitätsRechenZentrum

Fakultät für Mathematik und Informatik

- Introduction
- Known Solutions until 1992
- State of the Art 1997
- About the implemented Algorithm
- Online Access to the Database
- Latest Calculations
- Open Conjectures
- Symmetry Remarks
- A Superficial Explanation
- Sub No-3-in-line Solutions
- Submit a Configuration
- Distribution of Markers
- References until July 1992
- Corrections to published Data
- Summary in Tabular Form
- Update for n=17 and n=18 from March 2006
- New solution for n=28 with orthogonal reflection symmetry

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 of 1997**.
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 indicated by the alphabet 0,1,2,...,9,A,B,C...,Z,a,b,...,z only in their column positions from top to bottom row and in every row from left to right.
A coded configuration 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 - In March 2005 Gabor Ellmann discovered an error in Guy & Kellys published derivation of 1968.
- If this geometric/algebraic transformation-mistake is corrected it results: asymptotically are only
*PI/3*points selectable.^{1/2}n = 1.814... 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 miscount. 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

2023-09-30 20:49 UTC+2