[Question]
  [
Note: this problem was inspired by the [Unsolved Mathematical Problems for K-12](https://www.youtube.com/watch?v=JPhqhZvXlhQ) youtube video, which also features other interesting puzzles.
*From the [wikipedia article](https://en.wikipedia.org/wiki/No-three-in-line_problem):*
> 
> 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](https://en.wikipedia.org/wiki/Collinearity) ..... 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](https://tio.run/##bVHBaoNAFLzvVwyRkLW1Iemx4Cm00EsLIQchSJC4JrvKKquhpj9v365JY20EffNmxnlvtTo3x1I/d50HqatTg@YoUMtvgTJz@GBkilI7nElTNyikFoHte1KjpXto06JtiLK@mjGNkKIbbpKvnRvBfZ85e4jtgERWGkiywiT6ILj2Y8Yia4rZP@mFObsacZCZ22Qr462KEYaYeTPLI5onVSV0yrkMoGgDJuvdvizskomhKRtzEuM5hdA88u8Mk4/LADfVyflNViMZsg0gzzSYqqKaU83PNDWymy7ioAdLB9SVUVcmvzK5ZVxgBk4BT5Tm4wFctYRl69sjc2UF2Qu5FVTbr4HRmd@SohZOqAz9IkzeP1af6/XraoOkAZ@mAaapH9xBE0zB75@KPu0l7ZI16brlgs3p8jz7JOiqZ6FDFrOesT27kNQN4cDw57Vb2O@IHw) 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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest code in bytes wins!
## Examples
### Input
```
2
3
4
5
10
```
### Output
*'#' represents an occupied point, '.' represents an empty square*
```
##
##
.##
#.#
##.
.##.
#..#
#..#
.##.
..#.#
.##..
...##
#..#.
##...
....##....
..#....#..
.#......#.
...#..#...
#........#
#........#
...#..#...
.#......#.
..#....#..
....##....
```
  
[Answer]
# 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!](https://tio.run/##NY/BasMwEER/Rb44q2ilpoFe2qxCycVfYGzStJjUMg6WFORi7JB/d@XQ7mXmDczCXKqh6s@hvf5I57/reTYEDi0dlVLvIVQTOH5StrrCF@n/QJm262DDOTYEB7xx0lb13tYAAadI4Y8GHCMNn7c0PcCIOU0YeDzSibs3EKMlIB1tgeXDZKQhl1TyO2SSCp6m@RoKGf9QtoZSTrG@37yG43gikSQGnBRioactWo7PsWBn4wM4Rmz7xhzbEXuJKgRnZ@9639Wq8w2YZcjFtw5WH27FmWAPnX8B "JavaScript (Node.js) – 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](https://tio.run/##bVFRa4MwGHzPrzgaSuPmZBvsZeBT2WAvG5Q@CEWKzNgmSpRomd2fd19iS4vrg@Zyd9x9nzbHbl@b52HgUKY5dOj2Eq36lagLj3dW5aiNx4WybYdKGRm6@0ga9PRc24zsO6Kcr2XMIKboTtjsZ@srRBAwb4@xuSJR1BaKrLCZ2UlhgpSxxJlS9k96Zd6uJxxU4SfZqHSjU8QxFnzheCRR1jTS5EKoEJomYKrdfteVGzKz1LK2BzntqaQRSXCjTN0/hbioXi4vsp7IUH0IdaRiOjWdJZ3lkVoTN@ljGo7gyQN9ZvSZKc9M6RgfWEBQwAOlBbiD0D1h1QduZaGdoEahdILuxzEw2fk9q1rphcbSL8Ls43P5tVq9LdfIOoh5HmKeB@ENNMMc4vZW9GlPaaes2TC8MM6jKGL04hEjxDmLHMUcwf8A)):
$$\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](https://tio.run/##bVHBaoNAFLzvVwxZQtbWSttDDwVPoYVeWgg5CEGC1DXZVVZZDTX9eft2TUiwEdf3nBlm3tPm2O1r8zwMHMo0hw7dXqJVvxJ14fudVTlq4/tC2bZDpYwM3fsIGvR0rmVG9h1BTtcyZhCTdSds9rP1ESIImJfH2FyBKGoLRVLYzOykMEHKWOJEKftHvTIv1xMMqvCTbFS60SniGAu@cDiSKGsaaXIhVAhNEzDVbr/ryg2ZWUpZ24Oc5lTSiCS4Eabun0JcWE@XF1pPaKg@hDpSMFVNtaRaHik1cZM@puHYPPlGnxF9RsozUjrEGxYQZPBAbgHuIHRPveoDt7LQjlAjUTpC9@MYmOz8nlWt9ERj6Rdh9vG5/Fqt3pZrZB3EPA8xz4PwRjfDHOL2VvRpT24nr9kwvDDOI7oYHR5xRg@6GXfVgxEnMHKiPw)):
$$\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[]
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 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!](https://tio.run/##NY5BC8IgGIb/SiWEgjEadFqGhy4FQqxBB/EgKU5oGiYRre2vmyO6ve/z8b08nYyt7mS0V5kMSVCR9QgDqaVTvju4qI0OaOwBBkN1ae1Nc8gIky/Ee8bhm4CK8SYUFO6tNN7JG39jIJYFzQtG81WJS4EEyqBXuNZPHR6aqkHg35v6hyZI97j76SgGsSs/nybwo7eOZjAnJcCTWfiZiKrx5xisMwUFeVqhZTrlGrPHYrHdTWxm@EaglL4 "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~62~~ ~~53~~ 43 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
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](https://tio.run/##AU4Asf9vc2FiaWX//0wz4oC5xZPDqknQuFtELnJJwqNEzrXGtk4@zrTigJp94oKsYMqSw5/EgH0zLsOGypJ7w7wtYFIqw4t9Z18jXP9dSsK7/zU).
**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
```
[Answer]
# [R](https://www.r-project.org/), 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!](https://tio.run/##PY/NToQwFIX3PgVWQ3rHqxkGV8PceYSu3CGLTi0JsX@WkmAIz44lGnffl9x7ck7clrui6C/PWz85lQbvuIDF0ukgGkXK25vj1dliDU3UQcu0BEo8oxmUTJpbHKUNRucjgSd8A4DGk5UpDjM/okCRvQ0dVc04We6ByJZldd1llCGY7/zplDdcAf5XmOErcnUb3AcPrWpx7rDD6lwfjk8VwGOU7vNSA5Rl1GmKLseu61YUgl7zGE993rBD66/HjtgD@5X7HbO/7J7bc4Hs3TH4syDHPMgDjjoQY9gPxlAOWrcf "R – 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)}}
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 83 bytes
```
ＮθＷ‹№ω#⊗θ¿⁼Ｌω×θθ≔⁺…ω⊟⌕Ａω#¦.ω«≔⁻÷⌕Ａω#θ÷Ｌωθη≔⁻﹪⌕Ａω#θ﹪Ｌωθζ≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω»⪪ωθ
```
[Try it online!](https://tio.run/##bZHLbsMgEEXX9VcgsgGJZNdVVlbSSpaSylL7A45NA@oYbANxk6rf7o4frZOobEYw9555kKusyW0GXZeYKviXUB5kw2q@jlqlQRK2k86xjQ3Gs1YQuqBckK0NB5AFyjgn@p2wpzpk4FBrjl6xFiVvupSO1YIMmtg5fTQshYCscw5yo2zV81IMz9oUMcAvnqObrvoyLXYhwUnyFT1MhL02iEiM3@qTLuS9ty8nyJy@aqjuuQqJt6i9LQLY/zlT7h5yuYIME6Ep9okp5CejixXFmzkzNYZ5WnwAdE@rGvfzMTsvghj@t7jyJgF8PONKvqO00fgdrxXo4VOwq3XXPXbLE/wA "Charcoal – Try It Online") Link is to verbose version of code. Brute force so too inefficient for `n>5`. Explanation:
```
Ｎθ
```
Input `n`.
```
Ｗ‹№ω#⊗θ
```
Repeat until a solution was found.
```
¿⁼Ｌω×θθ
```
Have we reached the end of the grid?
```
≔⁺…ω⊟⌕Ａω#¦.ω«
```
In that case, one of our `#`s must have been placed incorrectly. Backtrack to the last one and replace it with a `.`, otherwise:
```
≔⁻÷⌕Ａω#θ÷Ｌωθη
```
Get the list of indices of the `#`s so far, convert to rows, and subtract the current row from each, giving the relative rows.
```
≔⁻﹪⌕Ａω#θ﹪Ｌωθζ
```
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:
```
ＮθＷ‹№ω#⊗θ¿‹№ω#⊗÷Ｌωθ≔⁺…ω⊟⌕Ａω#¦.ω«≔⁻÷⌕Ａω#θ÷Ｌωθη≔⁻﹪⌕Ａω#θ﹪Ｌωθζ≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω»⪪ωθ
```
[Try it online!](https://tio.run/##fZFNTsMwEIXX5BSWu7Elt1sWXUUtSJFoFQkukCamtpjYaWw3tIizm0lSFFoB3ozsN@@bH5eqaEtbQIyZaYLfhnonW3bgy6RTGiRhT9I5trLBeNYJQmeUC7K2YQeywjTOiX79Pykzfq2PupKYZfZesQ7FwZk6p/eG5RDQfCpBrpRtekCO4VGbKgX45nE00UXP7bA3CU6Sj@TuQthog4ip0I23LyfIX30IopB4jdrYKoD9nXPRbiHnH5BhIjSlPjOVfGd0tqB4MyemxjBNiw@A7odDKMCxF11Lx94m51kQ09NHob4SgI9nXMlnkrca9//cgB5@Abtaxngf50f4Ag "Charcoal – Try It Online") Link is to verbose version of code.
[Answer]
# [MATL](https://github.com/lmendo/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!**](https://tio.run/##y00syfn/P8HdqkTRS0u7pMQw1d01qqhETTdC3901olI7OKWuKjZX7f9/YwA)
### 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
```
[Answer]
# [Java (JDK)](http://jdk.java.net/), 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!](https://tio.run/##fVLBjpswEL3nK9xISezaYWFX6mHNsGorVeqhpz1GHAwYZEoGZMw2KM23p4awPbSrPaAZ8968Z95Qqxe1r4ufV3PsWutI7c/B4EwTfLZWjb1c/QeUA@bOtBh8Wxq5WnVD1pic5I3qe/JDGSTnFSHL294p58tLawpy9Bh9dtZgdUiJslXPZiohr2rxd3S60lYQg@6QJqQkQK64T87@TPwUoP41Y5gKI6xQIhOF0KIWJzGKXJatpf9@RlCapqGVeGBSsvPEMLCPhIVIcm5i3NoklBaqg0mTKI7xaerg4TFkE1dikBn3tR3QUc4niH2Ae8lmKwsGQuk1PqKc2QrMHYoMzAZFDV5e0uqg0q3XzVgSbuuZan9DnkRP0WJxgvoO90qMUHO@wX0mcghFAYqfhIaMj7JIINwW/qp6anSMsuDgQQ4jyzl4j2L20N5jkpWmpDaOmNVusEgqeblc5Zy09yN0CtP4ZO@lLzGQT75y/roMcgufWN0PjfO0MlBd14zUMLkQnsfe6WPQDi7o/Dpdg3TJ2rW3BdPbNPs7MufufZE8LspsQd6Uu6kEfuqoHF1v1tzwdb8Wyw/ifb4YVHZc3JCxwOquUbmmO7ITu3DH3rvtgl1W03O5/gE "Java (JDK) – 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
* -8 bytes and a pretty printer thanks to [Kevin Cruijssen](https://codegolf.stackexchange.com/users/52210/kevin-cruijssen).
* -1 byte thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)
]