Metraipolis › archive › dc_cd25f4385061
Three methods, one problem: Classical and AI approaches to no-three-in-line — arXiv:2512.11469
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2512.11469
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:49:11.701Z
- SHA-256 of the archived text
89216f865182f876a34eb8d18b80114f8bf32150fc410cf69b52c1cdacd3f4f6- Stable URL of this page
https://metraipolis.com/documento/dc_cd25f4385061
How to cite
Three methods, one problem: Classical and AI approaches to no-three-in-line — arXiv:2512.11469 — arXiv (en), https://arxiv.org/abs/2512.11469 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd25f4385061 (Metraipolis archive dc_cd25f4385061, sha256 89216f865182f876a34eb8d18b80114f8bf32150fc410cf69b52c1cdacd3f4f6)
BibTeX
@misc{dccd25f4385061,
title = {Three methods, one problem: Classical and AI approaches to no-three-in-line — arXiv:2512.11469},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2512.11469},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd25f4385061; sha256 89216f865182f876a34eb8d18b80114f8bf32150fc410cf69b52c1cdacd3f4f6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2512.11469. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The No-Three-In-Line problem asks for the maximum number of points that can be placed on an n by n grid with no three collinear, representing a famous problem in combinatorial geometry. While classical methods like Integer Linear Programming (ILP) guarantee optimal solutions, they face exponential scaling with grid size, and recent advances in machine learning offer promising alternatives for pattern-based approximation. This paper presents the first systematic comparison of classical optimization and AI approaches to this problem, evaluating their performance against traditional algorithms. We apply PatternBoost transformer learning and reinforcement learning (PPO) to this problem for the first time, comparing them against ILP. ILP achieves provably optimal solutions up to 19 by 19 grids, while PatternBoost matches optimal performance up to 14 by 14 grids with 96% test loss reduction. PPO achieves perfect solutions on 10 by 10 grids but fails at 11 by 11 grids, where constraint violations prevent valid configurations. These results demonstrate that classical optimization remains essential for exact solutions while AI methods offer competitive performance on smaller instances, with hybrid approaches presenting the most promising direction for scaling to larger problem sizes. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO). Categorie arXiv: Artificial Intelligence (cs.AI) ; Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2512.11469 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T14:32:29.901Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).