Constraint satisfaction programming for the no-three-in-line problem

Abstract

Using a constraint satisfaction formulation with rotational symmetry reduction, we exhibit configurations of 2 n points on the n × n grid for every 2 ≤ n ≤ 60 with no three collinear. These computations resolved every previously open case through n = 60 . We describe the formulation, computational search, and empirical scaling of the method.