No-Three-in-a-Line Problem

For , it is possible to select lattice points with such that no three are in a straight line (where "straight line" means any line in the plane--not just a horizontal or vertical line). The number of distinct solutions (not counting reflections and rotations) for , 2, ..., are 1, 1, 4, 5, 11, 22, 57, 51, 156 ... (OEIS A000769). For large , it is conjectured 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 (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)

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. These discoveries fill the remaining gaps up to , so configurations with points are now known for every grid with . Flammenkamp's page illustrates the record 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 .