A219760 Martin Gardner's minimal no-3-in-a-line problem.

1, 4, 4, 4, 6, 6, 8, 9, 10, 10, 12, 12, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25, 26, 26, 28, 29, 30

Offset

1,2

Comments

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

Links

Table of n, a(n) for n=1..29.

Alec S. Cooper, Oleg Pikhurko, John R. Schmitt, and Gregory S. Warrington, Martin Gardner's minimum no-3-in-a-line problem, Amer. Math. Monthly, 121 (2014), 213-221 (on JSTOR), DOI: 10.4169/amer.math.monthly.121.03.213. Also on arXiv, arXiv:1206.5350 [math.CO], 2012-2014.

Andy Huchala, Python program.

Seunghwan Oh, John R. Schmitt, and Xianzhi Wang, Repeatedly applying the Combinatorial Nullstellensatz for Zero-sum Grids to Martin Gardner's minimum no-3-in-a-line problem, arXiv:2401.03119 [math.CO], 2024. See page 3.

Gregory S. Warrington, Illustration for n=8

Crossrefs

Cf. A000769, A277433.

Sequence in context: A116446 A102126 A277433 * A097918 A256416 A256417

Adjacent sequences: A219757 A219758 A219759 * A219761 A219762 A219763

Keyword

nonn,hard,more

Author

N. J. A. Sloane, Nov 29 2012

Extensions

Terms a(13)-a(18) from Rob Pratt, Mar 29 2014

Terms a(19)-a(27) from Rob Pratt, Sep 05 2014

a(28)-a(29) from Andy Huchala, Apr 20 2024

Status

approved