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

Author

N. J. A. Sloane, Nov 29 2012

Keywords

• nonn
• hard
• more

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

• 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.
• Sandi Klavžar, James Tuite, and Ullas Chandran, The General Position Problem: A Survey, arXiv:2501.19385 [math.CO], 2025. See pp. 39, 58.
• 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.
• S. V. Ullas Chandran, Sandi Klavžar, and James Tuite, The General Position Problem: A Survey, arXiv:2501.19385 [math.CO], 2025. See pp. 41, 60.
• Gregory S. Warrington, Illustration for n=8

Crossrefs

Cf. A000769, A277433.

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