North-East Lattice Paths Avoiding $k$ Collinear Points via Satisfiability
This work provides improved bounds for a combinatorial problem in discrete geometry, but the improvement is incremental.
The authors used a SAT solver to enumerate all north-east lattice paths avoiding k collinear points for k ≤ 6, and found a path avoiding 7 collinear points with 327 steps, improving the previous best of 260 steps.
We investigate the Gerver-Ramsey collinearity problem of determining the maximum number of points in a north-east lattice path without $k$ collinear points. Using a satisfiability solver, up to isomorphism we enumerate all north-east lattice paths avoiding $k$ collinear points for $k \leq 6$. We also find a north-east lattice path avoiding $k = 7$ collinear points with 327 steps, improving on the previous best length of 260 steps found by Shallit.