The no-three-in-a-line problem asks how many lattice points with ,
for positive integer
, can be selected with no three collinear.
At most
such points can be selected, since every horizontal line contains at most two selected points.
Here, collinearity is with respect to any straight
line in the plane, not only horizontal
or vertical lines. The numbers of distinct solutions (not
counting reflections and rotations)
for
, 3, ..., are 1, 1, 4, 5, 11, 22, 57, 51, 156, ...
(OEIS A000769). For large
, the conjecture is that
it is only possible to select at most
lattice points
with no three collinear, where
|
(1)
| |||
|
(2)
|
(OEIS A093602; Guy, pers. comm., Oct. 22, 2004), correcting Guy and Kelly (1968) and Guy (1994, p. 242) who found .
Selected configurations are illustrated above. Some large known no-three-in-a-line configurations are summarized in the following table. The entries are listed by Flammenkamp (2026).
| rotation class | discoverer | |
| 52 | rot4 | Flammenkamp |
| 65 | rct4 | Heule (Jun. 18, 2026) |
| 67 | rct4 | Heule (Jun. 21, 2026) |
| 68 | rot4 | Prellberg (Mar. 23, 2026) |
| 69 | rct4 | Heule (Jun. 21, 2026) |
| 70 | rot4 | Heule (Jun. 17, 2026) |
| 71 | rct4 | Heule (Aug. 17, 2026) |
| 72 | rot4 | Heule (Jun. 25, 2026) |
| 73 | rct4 | Heule (Aug. 19, 2026) |
| 74 | rot4 | Prellberg (Jul. 20, 2026) |
| 76 | rot4 | Heule (Aug. 10, 2026) |
| 78 | rot4 | Prellberg (Oct. 28, 2026) |
The date listed for is its presentation date. Here, rot4 denotes quarter-turn
rotational symmetry and rct4 denotes quarter-turn
symmetry except on the long diagonals.
(The full symmetry is either half-turn rotational
symmetry or both diagonal reflections.) Heule's
solutions were found using a Boolean satisfiability
(SAT) solver.
Prellberg's configuration for ,
found on Oct. 28, 2026, is illustrated above. It has 156 points
and quarter-turn rotational symmetry, and
is the largest reported example (Flammenkamp 2026). As of Oct. 29, 2026, configurations
with
points are known for every
point lattice with
except
and 77. Flammenkamp (2026) gives many additional configurations and counts.
Pegg (2026a) gives a Wolfram Language notebook for checking configurations by searching for extraordinary lines,
i.e., lines containing at least three selected points,
and reports Prellberg's enumeration of 118057 solutions for .
A minimum variant asks for the smallest no-three-in-a-line subset of an point lattice that is maximal, i.e., such that adding
one more counter on any vacant lattice point produces
three on a line. The corresponding numbers for
, 2, ... begin 1, 4, 4, 4, 6, 6, 8, 8, 8, 8, 10, 10,
... (OEIS A277433; Aichholzer et al. 2023).
Aichholzer et al. (2023) study this problem as a general
position version of the geometric dominating set
problem. Pegg (2026b) gives additional examples and computations for this minimum
variant.
The three-dimensional no-three-in-a-line problem asks for the largest number
of points in the
integer lattice
with no three collinear in ordinary Euclidean
space. The figure shows the three horizontal layers of a 16-point configuration
for
supplied by Kudriashov (2026). The recorded values for
, 2, ... begin 1, 8, 16, 28, 40, 64, ... (OEIS A399138; Kudriashov 2026). Larger constructions
give lower bounds rather than known exact values. In particular, Kudriashov (2026)
gives
and
, improving the 93-point example illustrated
by Pegg (2026c). This sequence received an honorable
mention in the OEIS 400K celebration contest (OEIS Foundation Inc. 2026).
Each of the lines parallel to a fixed coordinate axis contains at most
two selected points, giving
. Pór and Wood (2007, pp. 482-485)
proved
, where
denotes asymptotic
notation. Their construction includes the
points
with
for any prime
. The third coordinate is reduced modulo
, but the prohibition is on collinearity
in Euclidean space.