News

A 120-year-old puzzle, a new world record, and a student project

Centre for Complex Systems 

20 November 2026

The record no-three-in-line configuration found by Prellberg: 156 golden points on a 78 × 78 grid, with no three lying on a straight line. Teal line segments join every pair of points.
The record no-three-in-line configuration found by Prellberg: 156 golden points on a 78 × 78 grid, with no three lying on a straight line. Teal line segments join every pair of points.

Two recent studies led by Thomas Prellberg, Professor of Mathematics in the Centre for Complex Systems (CCS), have attracted media coverage. One of them is authored by Prellberg alone. The other one is the result of an undergraduate research internship of Queen Mary student Pranav Ramanathan, carried out within the university's STRIDE programme in summer 2025 after his second year. After graduating this past summer, Pranav has moved on to do an MSc in Machine Learning at UCL.

Both works tackle the no-three-in-line problem, first posed by the puzzle-writer Henry Dudeney in 1900 as a chessboard puzzle. It asks how many points can be placed on a square grid without any three lying on a straight line, in any direction. On an n × n grid, the upper limit is 2n points, since each row can contain at most two. Whether this limit can be attained on arbitrarily large grids remains unknown.

Prellberg's paper "Constraint satisfaction programming for the no-three-in-line problem" uses constraint programming to find 2n-point solutions for every grid size up to 60 × 60. A feature in Scientific American describes this and later computational progress by Prellberg and, independently, by Marijn Heule of Carnegie Mellon University, who used SAT solvers. The latest record is Prellberg's October construction of 156 points on a 78 × 78 grid.

The second study, whose first author is Ramanathan, was covered by the science news sites Scienmag.com and Bioengineer.org. The project also involved QMUL researchers Dr Matthew Lewis and Professor Christian Beck together with colleagues at Vizuara AI Labs. Their paper "Three methods, one problem: classical and AI approaches to no-three-in-line" compares three approaches on smaller grids: classical optimisation, transformer-based pattern learning, and reinforcement learning. Classical optimisation achieved the strongest results in the reported experiments.


Links to the external news articles:


Links to the original research articles:

People: Thomas PRELLBERG Christian BECK

Contact: Lennart Dabelow
Email: l.dabelow@qmul.ac.uk

Updated by: Lennart Dabelow