24
\$\begingroup\$

Note: this problem was inspired by the Unsolved Mathematical Problems for K-12 youtube video, which also features other interesting puzzles.

From the wikipedia article:

The no-three-in-line problem asks for the maximum number of points that can be placed in the n × n grid so that no three points are collinear ..... Although the problem can be solved with 2n points for every n up to 46, it is conjectured that fewer than 2n points are possible for sufficiently large values of n.

You must write a program or function which takes in an input \$ n \$ where \$ 2 \leq n \leq 46 \$, and returns/outputs an \$ n \times n \$ grid containing \$ 2n \$ points, such that no three points are collinear (lie on a single line, including diagonals). Here is a checker for your program.

Clarifications

  • Each point is represented as a square in the grid
  • Each square must have two states, representing whether a square contains a point or not.
  • You may return a 2D array of chars, a 1D array of strings, or a string with an arbitrary separator.
  • It is not expected for your solution to run in time for a \$ 46 \times 46 \$ grid, but it should for at least \$ n \leq 5 \$
  • This is , so the shortest code in bytes wins!

Examples

Input

2
3
4
5
10

Output

'#' represents an occupied point, '.' represents an empty square

##
##

.##
#.#
##.

.##.
#..#
#..#
.##.

..#.#
.##..
...##
#..#.
##...

....##....
..#....#..
.#......#.
...#..#...
#........#
#........#
...#..#...
.#......#.
..#....#..
....##....
\$\endgroup\$
7
  • \$\begingroup\$ "including diagonals" -- are all diagonals prohibited, or just 45 degree ones? \$\endgroup\$
    – Jonah
    Apr 16, 2020 at 17:31
  • \$\begingroup\$ @Jonah All diagonals \$\endgroup\$ Apr 16, 2020 at 17:33
  • \$\begingroup\$ This would actually make for a pretty good fastest-code challenge. \$\endgroup\$
    – mypetlion
    Apr 16, 2020 at 21:47
  • 1
    \$\begingroup\$ Is outputting a binary matrix allowed? What about a list of complex numbers? Or a list of point coordinates? \$\endgroup\$
    – Luis Mendo
    Apr 17, 2020 at 12:17
  • 3
    \$\begingroup\$ @LuisMendo My intention was to output some sort of grid, so only a binary matrix is allowed. \$\endgroup\$ Apr 17, 2020 at 15:32

7 Answers 7

10
\$\begingroup\$

JavaScript (ES6),  208 ... 197  196 bytes

Returns a binary matrix.

f=(n,m=[...Array(n)].map(_=>Array(n).fill(0)),g=(C,z)=>m.some((r,y)=>r.some((v,x)=>v^z&&C(x,V=y,r))))=>!n|g((x,y,r)=>g((X,Y)=>g(H=>(V-=Y)|(H-=X)&&V*(X-x)==H*(Y-y)))?0:r[x]=+!!f(n-++r[x]/2,m),1)&&m

Try it online!

Output

Only \$N=2\$ to \$N=5\$ can be processed on TIO. The output for \$N=6\$ was computed locally.

\$N=2\$:

$$\begin{pmatrix} 1&1\\ 1&1 \end{pmatrix}$$

\$N=3\$:

$$\begin{pmatrix} 1&1&0\\ 1&0&1\\ 0&1&1 \end{pmatrix}$$

\$N=4\$:

$$\begin{pmatrix} 1&1&0&0\\ 0&0&1&1\\ 1&1&0&0\\ 0&0&1&1 \end{pmatrix}$$

\$N=5\$ (check it):

$$\begin{pmatrix} 1&1&0&0&0\\ 1&0&0&1&0\\ 0&0&0&1&1\\ 0&1&1&0&0\\ 0&0&1&0&1 \end{pmatrix}$$

\$N=6\$ (check it):

$$\begin{pmatrix} 1&1&0&0&0&0\\ 0&0&0&1&0&1\\ 0&1&0&0&1&0\\ 1&0&1&0&0&0\\ 0&0&0&0&1&1\\ 0&0&1&1&0&0 \end{pmatrix}$$

Commented

f = (                     // f is a recursive function
  n,                      // n = input
  m = [...Array(n)].map(  // m[] = n x n output matrix,
    _ => Array(n).fill(0) //       initially filled with 0's
  ),                      //
  g = (C, z) =>           // g is a helper function taking a callback C and a flag z:
    m.some((r, y) =>      //   for each row r[] at position y in m[]:
      r.some((v, x) =>    //     for each value v at position x in r[]:
        v ^ z &&          //       if v is not equal to z:
          C(x, V = y, r)  //         invoke C(x, y, r) and copy y to V
      )                   //     end of inner some()
    )                     //   end of outer some()
) =>                      //
  !n |                    // force success if n = 0
  g((x, y, r) =>          // for each 0-cell at (x, y) on row r[]:
    g((X, Y) =>           //   for each 1-cell at (X, Y):
      g(H =>              //     for each 1-cell at (H, V):
        (V -= Y) |        //       update V to V - Y
        (H -= X)          //       update H to H - X
        &&                //       test if either V - Y or H - X is not equal to 0
        V * (X - x) ==    //       and (V - Y) * (X - x) is equal to
        H * (Y - y)       //       (H - X) * (Y - y), i.e (x, y), (X, Y) and (H, V)
                          //       are collinear
      )                   //     end of 3rd iteration
    )                     //   end of 2nd iteration
    ?                     //   if there's a pair of points collinear to (x, y):
      0                   //     do nothing
    :                     //   else:
      r[x] = +!!f(        //     do a recursive call:
        n - ++r[x] / 2, m //       set (x, y) and subtract 1/2 from n
      ),                  //     if falsy, unset (x, y) afterwards
    1                     //   use z = 1 for the 1st iteration
  ) && m                  // end of 1st iteration; return m[]
\$\endgroup\$
3
  • 4
    \$\begingroup\$ It currently is incorrect for n > 6. The checking program for the 6x6 board says INCORRECT at (0, 1), (1, 3), (2, 5) \$\endgroup\$
    – u-ndefined
    Apr 17, 2020 at 3:54
  • 2
    \$\begingroup\$ @KevinCruijssen The diff between (0,1) and (1,3) is (1,2), and it's the same diff between (1,3) and (2,5). And since one point is in common, those are definitely linear! \$\endgroup\$ Apr 17, 2020 at 7:16
  • 1
    \$\begingroup\$ @u_ndefined Thank you for reporting this. I misread the requirements and had to do a complete rewrite. \$\endgroup\$
    – Arnauld
    Apr 17, 2020 at 11:31
3
\$\begingroup\$

Wolfram Language (Mathematica), 185 bytes

(d=1~(r=RandomInteger)~{#,#};While[(M=Max)[{M[(z=#;M[Tr/@(Diagonal[z,#]&/@Range[-2,2])])&/@{d,Reverse@d}],M[Tr/@d],M[Tr/@Transpose@d]}]>2||Tr[Join@@d]!=2#,d=1~r~{#,#}];ToString/@#&/@d)&

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 62 53 43 bytes

L3‹œêIи[D.rI£DεƶN>δ‚}€`ʒßĀ}3.Æʒ{ü-`R*Ë}g_#\

Random brute-force approach, so obviously pretty slow (n=5 finishes between 15-45 seconds on average).

Output as a list of lines, with 10 instead of #. respectively.

-10 bytes thanks to @Grimmy.

Try it online.

Explanation:

L              # Push a list in the range [1, (implicit) input-integer]
 3‹            # Check for each whether it's smaller than 3
               # (so we'll have a list with 2 zeroes and input-2 amount of 1s)
   œ           # Take the powerset of this list
    ê          # Sort and uniquify the list of lists
     Iи        # Repeat each sublist in the list the input amount of times
[              # Then start an infinite loop:
 D             #  Duplicate the list of potential rows
  .r           #  Randomly shuffle it
    I£         #  And then leave just the first input amount of rows
 D             #  Duplicate it
  ε            #  Map each row to:
   ƶ           #   Multiply each by their 1-based index
      δ        #   For each inner value:
       ‚       #    Pair it with
    N>         #    the 1-based map-index
  }€`          # After the map: flatten one level
     ʒ  }      # Filter each coordinate to:
      ß        #  Get the minimum
       Ā       #  And check that it's NOT 0
               # (we now have a list of all coordinates for the 1-bits)
  3.Æ          # Get all possible triplets of the coordinates
     ʒ         # Filter the list of triplets by:
      {        #  Sort the coordinates from lowest to highest
       ü       #  For each overlapping pair of coordinates:
               #    [[ax,ay],[bx,by],[cx,cy]] → [[[ax,ay],[bx,by]],[[bx,by],[cx,cy]]]
        -      #   Subtract them from one another
               #    → [[ax-bx,ay-by],[bx-cx,by-cy]]
         `     #  Push them separated to the stack
          R    #  Reverse the second
           *   #  Multiply them
               #   → [(ax-bx)*(by-cy),(ay-by)*(bx-cx)]
            Ë  #  And check if they are equal
      }g       # After the filter: get the amount of remaining triplets
        _      # If this is 0 (thus none are remaining anymore):
         #     #  Stop the infinite loop
               #  (after which the duplicated list of binary rows is output implicitly)
          \    # (Else:) discard it before trying again in the next iteration
\$\endgroup\$
4
  • 1
    \$\begingroup\$ oLbʒ1¢2Q}Ijð0: => L3‹Jœê for -8. Or skip the J, since you S it later anyway. \$\endgroup\$
    – Grimmy
    Apr 23, 2020 at 7:17
  • \$\begingroup\$ @Grimmy Oh, very nice! That's indeed a lot better. Thanks for -10. :) \$\endgroup\$ Apr 23, 2020 at 7:37
  • \$\begingroup\$ Some more savings, I think. Change this to that. Not sure how it works with the rest of the solution, though. \$\endgroup\$
    – Grimmy
    Apr 23, 2020 at 7:42
  • \$\begingroup\$ @Grimmy Hmm, although a very nice golf, I'm not sure if it's useful in my current approach. The result should be a matrix of 1s and 0s. I could use your code for a different approach, but I end up at 44 bytes that way. Your approach results in a list of coordinates that should contain a 1 in a matrix of 0s of dimensions input x input, and my approach already has this matrix and checks if its valid by checking the coordinates containing 1s. \$\endgroup\$ Apr 23, 2020 at 8:05
2
\$\begingroup\$

R, 192 bytes

Outputs a binary matrix. Random brute, found the answer for N=5 in <60s only once.

function(N){m=2*N;c=combn(1:m,3);repeat{p=t(replicate(m,sample(1:N,2,T)));o=matrix(0,N,N);o[p]=1;sum(o)==m&&1>sum(sapply(1:ncol(c),function(x)qr(cbind(p[c[,x],],1:3*0+1))$rank<3))&&return(o)}}

Try it online!

Just started learning R, any help appreciated.

function (N) {
  m = 2 * N
  c = combn(1:m, 3)                        # all 3-point combinations
  repeat {                                 # indefinitely
    p = t(replicate(m, sample(1:N, 2, T))) # 2N random points
    o = matrix(0, N, N)
    o[p] = 1                               # output matrix
    sum(o) == m                            # is each point different?
      && 1 > sum(                          # is it a vector of FALSEs?
        sapply(1:ncol(c),                  # for each combination
          function(x)
            qr(
              cbind(
                p[c[,x],]                  # point coordinates
              ,1:3*0+1)                    # add (1,1,1) column
            )$rank < 3)                    # is the matrix rank 2 or less
        )
      && return(o)}}
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to the site! \$\endgroup\$
    – Luis Mendo
    Apr 18, 2020 at 20:15
  • 1
    \$\begingroup\$ The first && can be & to save a byte, but it will definitely make the performance quite a bit worse (since it will do the entire sapply every iteration even if sum(o)==m is already falsey). But that is codegolf I guess; we don't care too much about performance, as long as we can save some bytes. ;) And welcome to CGCC! Nice first answer. \$\endgroup\$ Apr 23, 2020 at 8:17
1
\$\begingroup\$

Charcoal, 83 bytes

NθW‹№ω#⊗θ¿⁼Lω×θθ≔⁺…ω⊟⌕Aω#¦.ω«≔⁻÷⌕Aω#θ÷Lωθη≔⁻﹪⌕Aω#θ﹪Lωθζ≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω»⪪ωθ

Try it online! Link is to verbose version of code. Brute force so too inefficient for n>5. Explanation:

Nθ

Input n.

W‹№ω#⊗θ

Repeat until a solution was found.

¿⁼Lω×θθ

Have we reached the end of the grid?

≔⁺…ω⊟⌕Aω#¦.ω«

In that case, one of our #s must have been placed incorrectly. Backtrack to the last one and replace it with a ., otherwise:

≔⁻÷⌕Aω#θ÷Lωθη

Get the list of indices of the #s so far, convert to rows, and subtract the current row from each, giving the relative rows.

≔⁻﹪⌕Aω#θ﹪Lωθζ

And again for the columns.

≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω

Check whether any of the pairs of relative offsets are collinear and if so append a . otherwise append a #.

»⪪ωθ

Print the solution once it has been found.

Tweaking the test for an invalid solution allows n=7 to be calculated on TIO at a cost of 3 bytes:

NθW‹№ω#⊗θ¿‹№ω#⊗÷Lωθ≔⁺…ω⊟⌕Aω#¦.ω«≔⁻÷⌕Aω#θ÷Lωθη≔⁻﹪⌕Aω#θ﹪Lωθζ≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω»⪪ωθ

Try it online! Link is to verbose version of code.

\$\endgroup\$
1
\$\begingroup\$

MATL, 41 39 37 36 34 33 bytes

`G:t!J*+tt1eGEZrt&-X/GEXy+Sd~z]m&

The output is a binary matrix.

Running time is random. Input 4 typically takes between 3 and 20 seconds on my computer.

Try it online!

Explanation

`          % Do...while
  G:t!J*+  %   Generate n x n matrix representing a grid of complex numbers a+j*b,
           %   with a, b = 1, 2, ..., n (*)
  t        %   Duplicate  
  t1e      %   Duplicate again and reshape as a row vector
  GEZr     %   Randomly choose 2*n entries, without replacement (**)
  t        %   Duplicate
  &-       %   2*n x 2*n matrix of pairwise differences between the chosen numbers
  X/       %   2*n x 2*n matrix with the angle of each of those (complex)
           %   differences, in radians (***)
  GEXy+    %   Add identity matrix of size 2*n x 2*n
  S        %   Sort each column
  d        %   Consecutive differences along each column
  ~z       %   Number of zeros
]          % End. A new iteration is run if the top of the stack is nonzero; that
           % is, if the matrix (***) has been found to have two equal elements in
           % the same column. That indicates that two points are aligned. This is
           % because three complex numbers A, B, C are aligned if and only if
           % there is one of them, say C, such that A-C and B-C have the same
           % angle. The identity matrix has been added to avoid zeros in the
           % diagonal, which would lead to incorrectly detecting alignment when
           % there are just two points at the same vertical position (their
           % complex difference has angle 0). Adding the identity matrix sets
           % those diagonal entries to 1 radian, that is, 1/2/pi of a whole turn.
           % Since the coordinates of the points are integer and pi is
           % irrational, an angle difference of 1 radian will never occur for any 
           % pair of points (at least theoretically; in practice there may be
           % numerical precision issues for huge grids).
m          % For each point in the copy of the n x n complex grid (*), determine
           % if it is present in the vector of chosen points (**). Gives an n x n
           % matrix containing true or false, which will be displayed as 1 or 0
&          % Configures the implicit display function so that it will only show
           % the top of the stack
\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 325 bytes

n->{int g[]=new int[n],i,r,a,b,d,e,j,x,y,c;for(java.util.Arrays.fill(g,3);;){for(i=-1,r=1;++i<n&r>0;r=g[i]>1<<n?g[i]=3:0)for(;n.bitCount(++g[i])!=2;);for(r=i=0;i<n*n;)for(a=i/n,b=i%n,j=++i;(g[a]&1<<b)>0&j<n*n;r|=c>1?1:0)for(x=j/n-a,y=j++%n-b,c=0,d=a+x,e=b+y;d>=0&d<n&e>=0&e<n;d+=x,e+=y)c+=(g[d]&1<<e)>0?1:0;if(r<1)return g;}}

Try it online!

Works in time on TIO for up to n = 6.

Explanation

(partial explanation)

This answer returns an int-array. Each int has exactly two bits set. The position of those bits represent the dots for that row.

The algorithm first makes sure that exactly two bits are set in each row. If that's the case, we go to the next part. If that's not the case, numbers are increased/reset until exactly two bits are set in each row.

We now have a grid with exactly 2 positions set each row.

For each of those positions, the algorithm checks each possible next position (on the right first, then each position downwards) and traces a line from the base position until the border, through each next positions. If the line goes through 0 or 1 set values, it goes to the next position.

If more than 1 positions are found, the algorithm will check the next grid.

Credits

\$\endgroup\$
2
  • \$\begingroup\$ @KevinCruijssen Thanks! I could get rid of z... by introducing 2 new variables ^_^' This won't be easily golfed. I guess someone has to come with a better algorithm to beat this beast drastically. I'm afraid I didn't have enough courage to try several algorithms. \$\endgroup\$ Apr 17, 2020 at 12:55
  • \$\begingroup\$ Suggest g[d]>>e&1 instead of (g[d]&1<<e)>0?1:0 \$\endgroup\$
    – ceilingcat
    Feb 11 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.