The Min and Max of the No-3-in-line problem
The Min and Max of the No-3-in-line problem
For Martin Gardner’s minimum no-3-in-a-line problem, we want the minimal number of lattice points in a region such that adding another point creates 3 points in a line in some direction.
https://oeis.org/A277433 is all slopes version of the sequence: 1, 4, 4, 4, 6, 6, 8, 8, 8, 8.
I have extended the upper bounds for this: 1, 4, 4, 4, 6, 6, 8, 8, 8, 8, 10, 10, 12, 12, 14, 14, 15, 16, 16, 16, 16, 18, 20, 20, 22, 24, 24, 24, 24, 25.
Here are my solutions for the Minimum No-3-in-line problem:
EDIT: These are improved by Dmitry Kamenetsky for values 16, 17 and 21.
EDIT 2: The 2022 paper Geometric Dominating Sets has improvements for values 20, 21, 22 and 30. The last is a modification of a 26-point position found by Bob Hearn.
https://oeis.org/A277433 is all slopes version of the sequence: 1, 4, 4, 4, 6, 6, 8, 8, 8, 8.
I have extended the upper bounds for this: 1, 4, 4, 4, 6, 6, 8, 8, 8, 8, 10, 10, 12, 12, 14, 14, 15, 16, 16, 16, 16, 18, 20, 20, 22, 24, 24, 24, 24, 25.
Here are my solutions for the Minimum No-3-in-line problem:
EDIT: These are improved by Dmitry Kamenetsky for values 16, 17 and 21.
EDIT 2: The 2022 paper Geometric Dominating Sets has improvements for values 20, 21, 22 and 30. The last is a modification of a 26-point position found by Bob Hearn.
Out[]=
|
|
|
|
| ||||||||||
|
|
|
|
| ||||||||||
|
|
|
|
|
For the Maximum No-3-in-line problem, there’s also been recent activity: MathWorld. Uni-bielefeld. Wikipedia.
The number of distinct solutions for n=1, 2, ..., are 1, 1, 4, 5, 11, 22, 57, 51, 156 ... (OEIS A000769).
On 25th June 2026 Marijn Heule found a new solution with record grid size n=72 in the rot4 symmetry class.
The number of distinct solutions for n=1, 2, ..., are 1, 1, 4, 5, 11, 22, 57, 51, 156 ... (OEIS A000769).
On 25th June 2026 Marijn Heule found a new solution with record grid size n=72 in the rot4 symmetry class.
Out[]=
size:72 points:144 |
The queens version of Martin Gardner’s minimum no-3-in-a-line problem, https://oeis.org/A219760 , is better studied.
1, 4, 4, 4, 6, 6, 8, 9, 10, 10, 12, 12, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25, 26, 26, 28, 29, 30
1, 4, 4, 4, 6, 6, 8, 9, 10, 10, 12, 12, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25, 26, 26, 28, 29, 30
For the minimum no-3-in-line problem, here are 102 point configurations I’ve compiled with assistance from Dmitry Kamenetsky and David Eppstein. If an outer border is white, the solution can work on smaller cases as well.
Out[]=
And here’s a version of code that gives coverage lines for each solution:
Out[]=
For the maximum no-3-in-line problem, there’s an existing Demonstration:
In[]:=
ResourceFunction["CreditedDemonstration"]["NoThreeInLineProblem"]
Out[]=
How about 3D? The maximal number of points in an order 3 lattice is 16. Order 4: 28. Order 5: 40. Order 6: 64 Not a sequence, yet.
A003142 Largest subset of 3 X 3 X ... X 3 cube (in n dimensions) with no 3 points collinear. 0, 2, 6, 16, 43, 124, 353
A003142 Largest subset of 3 X 3 X ... X 3 cube (in n dimensions) with no 3 points collinear. 0, 2, 6, 16, 43, 124, 353
The next two orders are at least 72 and 88: