Three methods, one problem: classical and AI approaches to no-three-in-line
Background The No-Three-In-Line problem asks for the maximum number of points that can be placed on an n × n grid with no three collinear, representing a famous problem in combinatorial geometry. Methods We compare three approaches: (i) integer linear programming (ILP) using Gurobi, (ii) transformer-based pattern learning via PatternBoost, and (iii) reinforcement learning using proximal policy optimization (PPO). Results ILP achieves provably optimal solutions up to 19 × 19 grids. PatternBoost matches optimal performance up to 14 × 14 grids, and finds 29 points on 15 × 15 grids (optimal is 30). PPO achieves perfect solutions on 10 × 10 grids but fails at 11 × 11 grids due to constraint violations. Across four fixed-timeout runs, ILP was reliable through n = 17, PatternBoost through n = 12, and PPO succeeded only once at n = 10. Conclusions Classical optimization remains essential for exact solutions, while AI methods offer competitive performance on smaller instances. Hybrid approaches combining solvers with learned heuristics appear most promising for scaling to larger grids.
Institutions
- Queen Mary University of London (GB)
Publication Details
- Journal
- Frontiers in Artificial Intelligence
- Published
- 2026-11-17
- DOI
- https://doi.org/10.3389/frai.2026.1799444
- Citations
- 6
- Primary Topic
- Constraint Satisfaction and Optimization
- Type
- article
- Field-Weighted Citation Impact
- 6.35
Funders
- Queen Mary University of London