Four Methods, One Problem: The No-Three-In-Line Problem

The No-Three-In-Line problem asks for the maximum number of points that can be placed on an $n \times n$ grid with no three collinear, a famous problem in combinatorial geometry. We compare four approaches: (i) integer linear programming (ILP) using Gurobi, (ii) transformer-based pattern learning via PatternBoost, (iii) reinforcement learning using proximal policy optimization (PPO), and (iv) a Scientific Machine Learning (SciML) method that recasts the problem as continuous energy minimisation solved by gradient flow on Apple Metal. ILP achieves provably optimal solutions up to $19 \times 19$ grids. PatternBoost matches optimal performance up to $14 \times 14$ grids and finds 29 points on $15 \times 15$ grids (optimal is 30). PPO achieves perfect solutions on $10 \times 10$ grids but fails at $11 \times 11$ due to constraint violations. SciML finds optimal $2n$ configurations up to $n = 18$ in several cases on Apple M2 (Metal) hardware without symmetry pruning, but reliability is non-monotonic: $n = 17$ achieves 0/10 in a 10-run sweep (success reproduced only for one seed), while $n = 18$ succeeds 9/10 runs. Continuous-relaxation methods extend the reach of learning-based solvers well beyond the discrete-search ceilings of PatternBoost and PPO, suggesting a productive new direction for combinatorial geometry.