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

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Three methods, one problem: classical and AI approaches to no-three-in-line

6 citations
Frontiers in Artificial Intelligence
Constraint Satisfaction and Optimization
6.35
article

Three methods, one problem: classical and AI approaches to no-three-in-line

article en
6 citations

Abstract

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.

Frontiers in Artificial IntelligenceVol. 9
Queen Mary University of London (GB)
Queen Mary University of London
Openalex Percentile: Top 3%
Constraint Satisfaction and Optimization
6.35
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon