Friedrich-Schiller-Universität Jena
UniversitätsRechenZentrum
Fakultät für Mathematik und Informatik

The No-Three-in-Line Problem

Index

Introduction

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.

Known Solutions until 1992

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.

State of the Art 1997

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

About the implemented Algorithm

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.

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

Show No-Three-in-Line Configuration

Symmetry class one of . : / - o c x + *
Size n positive integer decimal number
No if no index given show the next

Latest Calculations

and

Future Aims

Conjectures

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.
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/31/2 n = 1.814... n points selectable.
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!

A Superficial Explanation

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.

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.

Sub No-3-in-line Solutions

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.

Type in a possible no-three-in-line configuration in my standard notation (lead in by its symmetry class chararcter).
On submission it will be Decoded, Checked, (if valid) Confirmed and Showed figuratively

References until July 1992

Corrections to published Data

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 miscount. The correct value is 675 instead of 693, the value of all configuration with at least rot2 symmetry.

Update for n=17 and n=18 from March 2006

Sorry, but I forgot totally to indicate a computation of Benjamin Chaffin, Williamstown, MA, USA. In march 2006 he generated all solutions for n=17 and n=18 and he emailed me the corresponding total counts in the same month. Moreover he set up this webpage of his research results up to size n=18. Because this web-page disappeared I put all 6800 asymmetric configurations of grid size 17 and all 18853 asymmetric configurations of grid size 18, coded in standard notation, in this file for download.

New solution for n=28 with orthogonal reflection symmetry

In September 2023, Michael Collier from Perth, Western Australia, wrote a program to check all my published counts of nothree-in-line solutions. He run it and also was able to extend the search for valid configurations in symmetry class - up to n=30. So he discovered one new configuration for n=28 and showed that there are no solutions for n=30 in this orthogonal reflection symmetry class.
Any comments or questions please to my current Email-address

Back to my HomePage

Achim Flammenkamp
2023-09-30 20:49 UTC+2