TOPICS
No-Three-in-a-Line Problem
The no-three-in-a-line problem asks how many lattice points with 
, for positive
integer 
,
can be selected with no three collinear. For 
, it is possible to select 
such 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.
 | 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. 20, 2026) |
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. With Heule's 
and 73 discoveries, configurations with 
points are now known for every
point lattice with 
except 
. Heule's 
configuration is the largest currently known. Flammenkamp's
page illustrates the 
configuration and many additional configurations and counts.
Pegg (2026) 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's June 2026 post gives additional examples and computations for this
minimum variant.
See also
Integer Lattice, N-Cluster, Tic-Tac-ToeExplore with Wolfram|Alpha
References
Adena, M. A.; Holton, D. A.; and Kelly, P. A. "Some Thoughts on the No-Three-in-Line Problem." In Combinatorial Mathematics: Proceedings of the Second Australian Conference (Ed. D. A. Holton). Berlin, Germany: Springer-Verlag, pp. 6-17, 1974. https://doi.org/10.1007/BFb0057371.Aichholzer, O.; Eppstein, D.; and Hainzl, E.-M. "Geometric Dominating Sets." Comput. Geom. Theory Appl. 108, 101913, 2023. https://doi.org/10.1016/j.comgeo.2022.101913.Flammenkamp, A. "Progress in the No-Three-in-Line Problem." J. Combin. Th. Ser. A 60, 305-311, 1992.Flammenkamp, A. "Progress in the No-Three-In-Line Problem. II." J. Combin. Th. Ser. A 81, 108-113, 1998.Flammenkamp, A. "The No-Three-in-Line Problem." https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html.Gardner, M. Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed. New York: W. H. Freeman, p. 69, 1989.Guy, R. K. "Unsolved Combinatorial Problems." In Combinatorial Mathematics and Its Applications: Proceedings of a Conference Held at the Mathematical Institute, Oxford, from 7-10 July, 1969 (Ed. D. J. A. Welsh). New York: Academic Press, pp. 121-127, 1971.Guy, R. K. "The No-Three-in-a-Line Problem." §F4 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 240-244, 1994.Guy, R. K. and Kelly, P. A. "The No-Three-in-Line-Problem." Canad. Math. Bull. 11, 527-531, 1968.Guy, R. K. and Kelly, P. A. "The No-Three-Line Problem." Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, Jan. 1968.Pegg, E. Jr. "Math Games: Chessboard Tasks." Apr. 11, 2005. https://www.mathpuzzle.com/MAA/36-Chessboard%20Tasks/mathgames_04_11_05.html.
Pegg, E. Jr. "Progress in the No-Three-in-Line Problem."
Wolfram Community, May 11, 2026. https://community.wolfram.com/t/26861. Pegg, E. Jr. "The Min and Max of the No-3-in-Line Problem."
Wolfram Community, Jun. 27, 2026. https://community.wolfram.com/t/27121.Sloane,
N. J. A. Sequences A000769/M3252,
A093602, and A277433
in "The On-Line Encyclopedia of Integer Sequences."
Cite this as:
Weisstein, Eric W. "No-Three-in-a-Line Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/No-Three-in-a-LineProblem.html