No-Three-in-a-Line Problem

The no-three-in-a-line problem asks how many lattice points with 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 , 2, ..., 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 through 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)
72	rot4	Heule (Jun. 25, 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. The , 67, and 69 discoveries fill the remaining gaps up to , so configurations with points are known for every point lattice with . 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.