No three in line, 3D

[Ed Pegg]

For the No-3-in-line problem, there's a new record. 
Solution for n=70
On 17th June 2026 Marijn Heule of Carnegie Mellon University (Pittsburgh, Pennsylvania, USA) used a newly developed SAT (Boolean satisfiability) solver to find a solution for n=70 in the rot4 symmetry class.  

I thought I'd look at the 3D case.  for the n x n x n lattice, what is the 
maximal number of points so that no three are in a line?  
order 2:  8   -- solution left as an exercise.  
order 3:  16  --   https://oeis.org/A003142  
order 4:  28  
order 5:  40-45      Not sure how to solve this one.  

Related 
https://oeis.org/A219760  -- minimize 3-blocking in 2d  
https://oeis.org/A280537  -- no 4 in plane. 

pts3Max16 = {
{0, 0, 1}, {0, 0, 2}, {0, 1, 0}, {0, 1, 2},
{0, 2, 0}, {0, 2, 1}, {1, 0, 0}, {1, 0, 2},
{1, 2, 0}, {1, 2, 2}, {2, 0, 0}, {2, 0, 1},
{2, 1, 0}, {2, 1, 2}, {2, 2, 1}, {2, 2, 2}
};

pts4Max28 = {
{0, 0, 1}, {0, 0, 3}, {0, 1, 1}, {0, 1, 3},
{0, 2, 0}, {0, 2, 2}, {0, 3, 0}, {0, 3, 2},
{1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 2, 3},
{1, 3, 2}, {1, 3, 3}, {2, 0, 2}, {2, 0, 3},
{2, 1, 3}, {2, 2, 0}, {2, 3, 0}, {2, 3, 1},
{3, 0, 0}, {3, 0, 2}, {3, 1, 0}, {3, 1, 2},
{3, 2, 1}, {3, 2, 3}, {3, 3, 1}, {3, 3, 3}
};

The following may not be maximal:  
pts5AtLeast40 = {
{0, 1, 0}, {0, 3, 0}, {1, 0, 0}, {1, 1, 0},
{2, 3, 0}, {2, 4, 0}, {3, 0, 0}, {3, 2, 0},
{4, 2, 0}, {4, 4, 0}, {0, 1, 1}, {0, 3, 1}, 

{1, 0, 1}, {1, 3, 1}, {2, 4, 1}, {3, 0, 1}, 

{3, 1, 1}, {4, 2, 1}, {4, 4, 1}, {1, 1, 2}, 

{1, 4, 2}, {3, 3, 2}, {3, 4, 2}, {4, 1, 2}, 

{4, 3, 2}, {0, 0, 3}, {0, 2, 3}, {1, 3, 3}, 

{1, 4, 3}, {2, 0, 3}, {3, 1, 3}, {3, 4, 3}, 

{4, 1, 3}, {4, 3, 3}, {0, 0, 4}, {0, 2, 4}, 

{2, 0, 4}, {2, 3, 4}, {3, 2, 4}, {3, 3, 4}
};

[Martin Møller Skarbiniks Pedersen]

On Thu, 18 Jun 2026 at 20:21, Ed Pegg <edp...@gmail.com> wrote:
>
> For the No-3-in-line problem, there's a new record.
> Solution for n=70
> On 17th June 2026 Marijn Heule of Carnegie Mellon University (Pittsburgh, Pennsylvania, USA) used a newly developed SAT (Boolean satisfiability) solver to find a solution for n=70 in the rot4 symmetry class.

OK. Then I guess https://oeis.org/A272651 should be updated. It only
shows the values up to 64.

[Lucas Brown]

You could extend this down to the order 1 case, which would give you enough known terms to submit a sequence.

—LAB

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAGAA5bcSOW3LrRD7C7e1B%3D%3DjzwZcWHeGU3yV09PzkYV%2B8LDYbw%40mail.gmail.com.

[Lucas Brown]

I am attaching two Python files: no-3-in-line_3d.py and no-3-in-line_3d_cpsat.py.

The first file uses a backtracking algorithm that I wrote myself.  It is slow enough that I terminated it before it could finish the n=4 case, but at least I can trust its accuracy.

The second file was vibe-coded by ChatGPT.  It converts the problem to a SAT instance and feeds it into Google's CP-SAT solver (https://developers.google.com/optimization/cp/cp_solver).  It reproduces a(3) = 16 and a(4) = 28 in less than a second on my computer, but it spun its wheels for over an hour on the n=5 case.  After early termination, it printed text to the effect that 40 <= a(5) <= 43, and also printed an explicit list of 40 points to support the lower bound.  I do not know enough about this SAT solver to verify the vibecode, so make of that what you will.

—LAB

[Ed Pegg]

I took another look at the order 5 case myself.  I had a program find 40 point solutions and canonicalize them... and then kept running it.  119 solutions were found for 40 points, and then the solution set seemed saturated, with no extras found.  Not a proof that 40 points is maximal, but probably.
no-3-in-line-3D  so far
1, 8, 16, 28, 40.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CALSFKfhm6LtU%2Bf42m31x-LFwSVKu6JowJg-RnJs07FHYcwxEMA%40mail.gmail.com.

[Ed Pegg]

Opening shot at order 6: 64 points.   72 points is the current upper bound. 

pts6AtLeast64 = {{0, 0, 3}, {0, 0, 5}, {0, 1, 1}, {0, 1, 3}, {0, 2,
   4}, {0, 2, 5}, {0, 3, 0}, {0, 3, 1}, {0, 4, 2}, {0, 4, 4}, {0, 5,
   0}, {0, 5, 2}, {1, 0, 1}, {1, 0, 3}, {1, 1, 0}, {1, 2, 2}, {1, 2,
   5}, {1, 3, 0}, {1, 3, 3}, {1, 4, 5}, {1, 5, 2}, {1, 5, 4}, {2, 0,
   4}, {2, 0, 5}, {2, 1, 2}, {2, 1, 5}, {2, 2, 1}, {2, 3, 4}, {2, 4,
   0}, {2, 4, 3}, {2, 5, 0}, {2, 5, 1}, {3, 0, 0}, {3, 0, 1}, {3, 1,
   0}, {3, 1, 3}, {3, 2, 4}, {3, 3, 1}, {3, 4, 2}, {3, 4, 5}, {3, 5,
   4}, {3, 5, 5}, {4, 0, 2}, {4, 0, 4}, {4, 1, 5}, {4, 2, 0}, {4, 2,
   3}, {4, 3, 2}, {4, 3, 5}, {4, 4, 0}, {4, 5, 1}, {4, 5, 3}, {5, 0,
   0}, {5, 0, 2}, {5, 1, 2}, {5, 1, 4}, {5, 2, 0}, {5, 2, 1}, {5, 3,
   4}, {5, 3, 5}, {5, 4, 1}, {5, 4, 3}, {5, 5, 3}, {5, 5, 5}}

[Ed Pegg]

order 7, at least 72.  
  pts7AtLeast72 = { {0, 1, 2}, {0, 1, 4}, {0, 2, 1}, {0, 2, 4}, {0, 3, 1}, {0, 3, 5}, {0, 4, 3}, {0, 4, 5}, {0, 5, 2}, {0, 6, 0}, {0, 6, 3}, {1, 0, 2}, {1, 0, 3}, {1, 1, 0}, {1, 1, 2}, {1, 2, 0}, {1, 3, 5}, {1, 3, 6}, {1, 4, 1}, {1, 4, 3}, {1, 5, 5}, {1, 5, 6}, {1, 6, 1}, {1, 6, 4}, {2, 0, 4}, {2, 0, 5}, {2, 1, 5}, {2, 1, 6}, {2, 2, 0}, {2, 2, 4}, {2, 5, 0}, {2, 5, 2}, {2, 6, 6}, {3, 0, 1}, {3, 0, 2}, {3, 1, 0}, {3, 1, 6}, {3, 2, 6}, {3, 3, 1}, {3, 5, 0}, {3, 6, 4}, {3, 6, 5}, {4, 0, 4}, {4, 1, 1}, {4, 3, 0}, {4, 4, 6}, {4, 5, 1}, {4, 5, 5}, {4, 6, 0}, {4, 6, 5}, {5, 0, 3}, {5, 0, 5}, {5, 1, 3}, {5, 1, 5}, {5, 2, 6}, {5, 3, 0}, {5, 4, 0}, {5, 4, 1}, {5, 5, 4}, {5, 5, 6}, {5, 6, 1}, {5, 6, 2}, {6, 1, 1}, {6, 2, 3}, {6, 2, 5}, {6, 3, 2}, {6, 3, 4}, {6, 4, 2}, {6, 4, 6}, {6, 5, 1}, {6, 5, 4}, {6, 6, 3} };

order 8, at least 91.    
pts8AtLeast91 = {
{0, 0, 2}, {0, 0, 3}, {0, 1, 1}, {0, 1, 5},
{0, 2, 5}, {0, 2, 6}, {0, 3, 1}, {0, 3, 3},
{0, 5, 4}, {0, 5, 6}, {0, 6, 2}, {0, 6, 7},
{0, 7, 4}, {1, 0, 3}, {1, 0, 5}, {1, 1, 1},
{1, 1, 5}, {1, 2, 2}, {1, 2, 3}, {1, 3, 0},
{1, 3, 7}, {1, 4, 0}, {1, 4, 6}, {1, 5, 4},
{1, 6, 1}, {1, 6, 7}, {1, 7, 4}, {1, 7, 6},
{2, 0, 0}, {2, 0, 6}, {2, 1, 0}, {2, 3, 2},
{2, 3, 7}, {2, 5, 1}, {2, 5, 3}, {2, 6, 3},
{2, 7, 1}, {2, 7, 2}, {3, 0, 1}, {3, 1, 7},
{3, 4, 0}, {3, 5, 1}, {3, 5, 6}, {3, 7, 5},
{3, 7, 7}, {4, 0, 4}, {4, 0, 5}, {4, 1, 7},
{4, 2, 0}, {4, 6, 0}, {4, 6, 5}, {4, 7, 6},
{4, 7, 7}, {5, 0, 2}, {5, 0, 4}, {5, 1, 0},
{5, 1, 6}, {5, 2, 0}, {5, 2, 6}, {5, 4, 7},
{5, 5, 7}, {5, 6, 1}, {5, 7, 1}, {5, 7, 3},
{6, 0, 1}, {6, 0, 7}, {6, 1, 2}, {6, 2, 1},
{6, 2, 5}, {6, 3, 2}, {6, 3, 6}, {6, 5, 0},
{6, 5, 3}, {6, 6, 0}, {6, 6, 6}, {6, 7, 3},
{6, 7, 5}, {7, 0, 6}, {7, 1, 3}, {7, 2, 1},
{7, 2, 3}, {7, 3, 0}, {7, 3, 6}, {7, 4, 2},
{7, 4, 7}, {7, 5, 5}, {7, 5, 7}, {7, 6, 4},
{7, 6, 5}, {7, 7, 0}, {7, 7, 2}
};

Unlike previous orders, I believe these can be beaten.

[Rob Pratt]

I confirmed via integer linear programming that a(5) = 40.

[Rob Pratt]

I confirmed via integer linear progamming that a(6) = 64.

[Ed Pegg]

Thanks, Rob.  

Also..  in the 2D case, solutions for orders 67 and 69 have been found.  
Solutions are known for all values up to order 70. 

To view this discussion visit https://groups.google.com/d/msgid/seqfan/6d15ee56-d231-4a60-b075-b6815d50662en%40googlegroups.com.

[Ed Pegg]

https://oeis.org/A277433 is in a sorry state solution wise.  

Here are two nice solutions.  

14x14 <= 12 
{{0, 0}, {0, 13}, {3, 6}, {3, 7}, {6, 3}, {6, 10}, {7, 3}, {7,10}, {10, 6}, {10, 7}, {13, 0}, {13, 13}}

18x18<=16  
{{1, 3}, {1, 14}, {6, 8}, {6, 9}, {7, 7}, {7, 10}, {8, 4}, {8,13}, {9, 4}, {9, 13}, {10, 7}, {10, 10}, {11, 8}, {11, 9}, {16,3}, {16, 14}}

⚫⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚫
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚫⚫⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚫⚪⚪⚪⚪⚪⚪⚫⚪⚪⚪
⚪⚪⚪⚫⚪⚪⚪⚪⚪⚪⚫⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚫⚫⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚫⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚫ 

⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚫⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚫⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚫⚫⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚫⚪⚪⚫⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚫⚪⚪⚪⚪⚫⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚫⚪⚪⚪⚪⚫⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚫⚪⚪⚫⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚫⚫⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚫⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚫⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪