Wolfram Cloud Page

After decades of no progress in the no-three-in-line-problem, in September 2025, Thomas Prellberg found “New Solutions for n=47,49,51,53,54,55,56 and n=58”. In January, “Solution for n=59 and n=60”. A whole bunch of new solutions followed, with March 2026, Solution for n=68.

In 1917, Henry Dudeney asked for the maximum number of points selectable from an

grid so that no three points are collinear. Obviously, no more than two points can be selected from any row or column, so the maximal amount of points is

. Calling a solution an

grid with a maximal selection of

points with no three points collinear, a 52×52 grid with 104 selected points is the largest known solution (as of 2023).

Here’s code from my Demonstration, No-Three-in-Line Problem.

In[]:=

known=

;ascii="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#$%&@?!()[]<>{}=*+|-/~^_:;,.";replace=Thread[Characters[ascii]Range[90]];nothree[dat_]:=ArrayPlot[Transpose[Normal[SparseArray[#1&/@Flatten[MapIndexed[Transpose[{#1,{#2[[1]],#2[[1]]}}]&,Partition[Drop[Characters[dat],1]/.replace,2]],1]]]],MeshTrue,PixelConstrained->6]

A sample item from data “known” is “:13062415240635”. After the first character, the first row has points at positions 1 and 3. The second row has points at positions 0 and 6. And so on.

In[]:=

nothree[":13062415240635"]

Out[]=

The title is stolen from a paper by Achim Flammenkamp (J. Combin. Theory Ser. A, 60 (1992)). He followed up with a (same title) II paper in 1998, which gave an order 52 solution, shown below. For decades, that was the end of the problem. It became an infamous problem with no progress.

In[]:=

nothree[Last[known]]

Out[]=

The first character is a symmetry class: “. : / - o c x + *”. What do those characters mean? We can look for representatives in the data.

Out[]=

In[]:=

Row[Riffle[Column[{StringTake[#,1],nothree[#]},Alignment->Center]&/@(First/@GatherBy[Select[known,StringLength[#]==37&],StringTake[#,1]&]),Spacer[10]]]

Out[]=

After decades of no progress, in September 2025, Thomas Prellberg found “New Solutions for n=47,49,51,53,54,55,56 and n=58”. In January, “Solution for n=59 and n=60”. A whole bunch of new solutions followed, with March 2026, Solution for n=68.

Out[]=

We can check the solution using extraordinary lines. An ordinary line is a line with two points. An extraordinary line is one with 3 or more points. A different problem minimizes ordinary lines in a configuration of points. Every 2D set of n points contains at least 6 n/13 ordinary lines. The no-3-in-line problem maximizes the ordinary lines. The point set above is collected in p68.

In[]:=

ResourceFunction["FindExtraordinaryLines"][p68]

Out[]=

{}

And there are no extraordinary lines. But if we add one point, we get some.

In[]:=

ResourceFunction["FindExtraordinaryLines"][Append[p68,{17,17}]]

Out[]=

{{1,17,137},{3,69,137},{14,43,137},{27,32,137},{33,34,137},{35,37,137},{49,134,137},{61,76,137},{73,87,137}}

Even if we go off the grid, we tend to find lines of 3.

In[]:=

ResourceFunction["FindExtraordinaryLines"][Append[p68,{74,75}]]

Out[]=

{{4,80,137},{99,115,137},{125,129,137}}

In[]:=

ResourceFunction["FindExtraordinaryLines"][Append[p68,{74,76}]]

Out[]=

{{19,105,137},{22,64,137},{112,136,137},{122,124,137}}

Yesterday, Thomas Prellberg enumerated the 118057 solutions for n=20. This is a very active problem at the moment. For more on this, see Mathworld: No-Three-in-a-Line-Problem, Wikipedia: No-three-in-line problem and Universität Bielefeld: The No-Three-in-Line Problem.

The enumeration seems to be exponential so far.

In[]:=