No-three-in-line problem: extend the record of n×n grids admitting 2n points with no 3 collinear
Statement
Place points on the $n\times n$ integer grid so that no three of them are collinear. At most $2n$ points are possible (pigeonhole: $2n+1$ points force three in some row or column). It is a longstanding open question whether the maximum equals $2n$ for every $n$. Exhibit a set of $2n$ points on the $n\times n$ grid with no three collinear for a value of $n$ where none is currently known, or prove that for some $n$ fewer than $2n$ is the maximum.
Acceptance. ADVANCES: exhibit an explicit $2n$-point no-three-collinear configuration on the $n\times n$ grid for some $n$ beyond the current verified record (i.e. $n\ge 61$), pushing the 'largest n with a known $2n$-solution' upward — verified by a script that confirms exactly $2n$ distinct grid points with no three collinear. FULLY RESOLVES (in either direction): a proof that $2n$ is achievable for all $n$, OR a specific $n$ together with an exhaustive-search certificate proving the maximum is $< 2n$. Deliver the point set + the collinearity-checking verifier and the $n$ attained.
Background
The no-three-in-line problem (Dudeney, 1917); a staple open problem in combinatorial/discrete geometry (Croft–Falconer–Guy, 'Unsolved Problems in Geometry', §F4; Brass–Moser–Pach). Upper bound $2n$ is elementary. Configurations of exactly $2n$ points are known for all small $n$; a 2026 constraint-satisfaction attack (arXiv:2602.07751) exhibited $2n$-point solutions for all $n\le 60$, so the smallest $n$ for which it is unknown whether $2n$ is achievable is currently $61$. Asymptotically, Hall–Jackson–Sudbery–Wild (1975) construct $(3/2 - \varepsilon)n$ points for all $n$, and Guy–Kelly's probabilistic heuristic conjectures that for large grids the achievable count falls strictly below $2n$ (to about $c\,n$ with $c=\sqrt[3]{2\pi^2/3}\approx 1.87$) — so it is widely believed $2n$ fails eventually, but no $n$ where it fails is known, and the exact threshold is open. The attacker's tool: this is a finite constraint-satisfaction / search problem — a candidate is a set of $2n$ lattice points, and 'no three collinear' is checked by testing all triples (or via slopes), so any construction is immediately machine-verifiable. Attack routes: SAT/CP-SAT and ILP encodings, symmetry breaking (the grid's dihedral group), and structured/algebraic constructions (e.g. modular hyperbolas) as warm starts.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | No-three-in-line problem (Wikipedia) | website |
| REF-02 | Constraint Satisfaction Programming for the No-three-in-line Problem | arxiv |
| REF-03 | Flammenkamp — No-Three-in-Line records | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.