This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A219760 #82 May 12 2025 12:00:51
%S A219760 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,
%T A219760 26,28,29,30
%N A219760 Martin Gardner's minimal no-3-in-a-line problem.
%C A219760 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.
%C A219760 From _Rob Pratt_, Mar 29 2014: (Start)
%C A219760 Can be computed by using integer linear programming (ILP) as follows.
%C A219760 The ILP formulation uses two sets of binary decision variables:
%C A219760 x[i,j] = 1 if a queen appears in square (i,j), 0 otherwise
%C A219760 y[k] = 1 if line k contains exactly two queens, 0 otherwise
%C A219760 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:
%C A219760 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]
%C A219760 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]
%C A219760 The objective is to minimize the sum of all x[i,j].
%C A219760 (End)
%C A219760 From _Don Knuth_, Aug 26 2014: (Start)
%C A219760 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.
%C A219760 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.
%C A219760 (End)
%C A219760 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
%H A219760 Alec S. Cooper, Oleg Pikhurko, John R. Schmitt, and Gregory S. Warrington, <a href="http://dx.doi.org/10.4169/amer.math.monthly.121.03.213">Martin Gardner's minimum no-3-in-a-line problem</a>, Amer. Math. Monthly, 121 (2014), 213-221 (on JSTOR), DOI: 10.4169/amer.math.monthly.121.03.213. Also on <a href="http://arxiv.org/abs/1206.5350">arXiv</a>, arXiv:1206.5350 [math.CO], 2012-2014.
%H A219760 Andy Huchala, <a href="/A219760/a219760_1.py.txt">Python program</a>.
%H A219760 Sandi Klavžar, James Tuite, and Ullas Chandran, <a href="https://arxiv.org/abs/2501.19385">The General Position Problem: A Survey</a>, arXiv:2501.19385 [math.CO], 2025. See pp. 39, 58.
%H A219760 Seunghwan Oh, John R. Schmitt, and Xianzhi Wang, <a href="https://arxiv.org/abs/2401.03119">Repeatedly applying the Combinatorial Nullstellensatz for Zero-sum Grids to Martin Gardner's minimum no-3-in-a-line problem</a>, arXiv:2401.03119 [math.CO], 2024. See page 3.
%H A219760 S. V. Ullas Chandran, Sandi Klavžar, and James Tuite, <a href="https://arxiv.org/abs/2501.19385">The General Position Problem: A Survey</a>, arXiv:2501.19385 [math.CO], 2025. See pp. 41, 60.
%H A219760 Gregory S. Warrington, <a href="/A219760/a219760.pdf">Illustration for n=8</a>
%Y A219760 Cf. A000769, A277433.
%K A219760 nonn,hard,more
%O A219760 1,2
%A A219760 _N. J. A. Sloane_, Nov 29 2012
%E A219760 Terms a(13)-a(18) from _Rob Pratt_, Mar 29 2014
%E A219760 Terms a(19)-a(27) from _Rob Pratt_, Sep 05 2014
%E A219760 a(28)-a(29) from _Andy Huchala_, Apr 20 2024