cp's OEIS Frontend

This means no three points on any line, not just lines in the X or Y directions.

A000755 gives the total number of solutions (as opposed to the number of equivalence classes).

It is conjectured that a(n)=0 for all sufficiently large n.

Flammenkamp's web site reports that at least one solution is known for all n <= 46 and n=48, 50, 52.

From R. K. Guy, Oct 22 2004: (Start)

I got the no-three-in-line problem from Heilbronn over 50 years ago. See Section F4 in UPINT.

In Canad. Math. Bull. 11 (1968) 527-531, MR 39 #129, Guy & Kelly conjecture that, for large n, at most (c + eps)*n points can be selected, where 3*c^3 = 2*Pi^2, i.e., c ~ 1.87.

As recently as last March, Gabor Ellmann pointed out an error in our heuristic reasoning, which, when corrected, gives 3*c^2 = Pi^2, or c ~ 1.813799. (End)

a(n) is the minimal number of counters that can be placed on an n X n chessboard, no three in a line, such that adding one more counter on any vacant square will produce three in a line.

From Rob Pratt, Mar 29 2014: (Start)

Can be computed by using integer linear programming (ILP) as follows.

The ILP formulation uses two sets of binary decision variables:

x[i,j] = 1 if a queen appears in square (i,j), 0 otherwise

y[k] = 1 if line k contains exactly two queens, 0 otherwise

Let SQUARES[k] be the set of squares that appear in line k, and let LINES[i,j] be the set of lines that contain square (i,j), so that (i,j) is in SQUARES[k] iff k is in LINES[i,j]. Then we have the following constraints:

2 y[k] <= sum {(i,j) in SQUARES[k]} x[i,j] <= 1 + y[k] for all lines k [no 3-in-a-line, and if y[k] = 1 then exactly two queens appear in line k]

x[i,j] + sum {k in LINES[i,j]} y[k] >= 1 for all squares (i,j) [either a queen appears in square (i,j) or some line that contains square (i,j) contains exactly two queens]

The objective is to minimize the sum of all x[i,j].

(End)

From Don Knuth, Aug 26 2014: (Start)

a(26)=26: there is a solution in which every queen appears in an odd-numbered row and an odd-numbered column, and furthermore cell (i,j) is occupied if and only if cell (j,i) is occupied. Such solutions exist when n=10, 18, 26. Conversely it's known that a(n)>=n when n is even.

There are many ways to place n+1 queens that satisfy the conditions, with queens occupying only "white" squares (if the top left corner square is white), at least for n<=30.

(End)

This is for the "queens" version of the problem, where "lines" are vertical, horizontal and diagonal only. The version where lines can have any slope is A277433. - Robert Israel, Oct 26 2016