cp's OEIS Frontend

A274947 Irregular triangle read by rows: T(n,k) (n>=0, 0 <= k <= n^2) = least number of squares attacked by k queens on an n X n board.

%I A274947 #61 Jul 28 2023 01:59:54
%S A274947 0,0,1,0,4,4,4,4,0,7,8,9,9,9,9,9,9,9,0,10,13,14,15,15,15,16,16,16,16,
%T A274947 16,16,16,16,16,16,0,13,18,20,21,22,23,23,24,24,24,24,24,25,25,25,25,
%U A274947 25,25,25,25,25,25,25,25,25,0,16,23,27,28,30,31,32,32,33,34,34,34,34,35,35,35,35,35,35,35,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36
%N A274947 Irregular triangle read by rows: T(n,k) (n>=0, 0 <= k <= n^2) = least number of squares attacked by k queens on an n X n board.
%C A274947 Place k queens on an n X n board so that the total number of squares attacked/occupied by the queens is minimized.
%C A274947 If enough terms were known, would provide an upper bound for A250000. For if A250000(n) = Q then T(n,Q) <= n^2 - Q, or equivalently A274948(n,Q) >= Q.
%C A274947 Values n^2 - T(n,n) are given in A001366.
%C A274947 Let X(n) be the smallest number so that no matter how you place X queens, they attack every square. That is, X is the minimal number such that T(n,k) = n^2 for all k >= X. Then X = n^2 - T(n,1) + 1 = A274948(n,1) + 1 = n^2 - 3*n + 3. More generally, T(n,k') <= n^2-k if and only if k' <= n^2-T(n,k). For example, we may place 2 queens on two squares of a 4 X 4 board and leave 4^2-T(4,2)=3 squares not attacked, so we may place 3 queens on these 3 squares instead and leave those two squares not attacked, ergo, T(4,3)=16-2. - _Andrey Zabolotskiy_, Jul 29 2016
%H A274947 Bernard Lemaire and Pavel Vitushinkiy, <a href="https://cs.nyu.edu/~gottlieb/tr/overflow/1996-may-jun-1.pdf">Placing n non dominating queens on the n X n chessboard. Part I</a>, French Federation of Mathematical Games.
%H A274947 Bernard Lemaire and Pavel Vitushinkiy, <a href="https://web.archive.org/web/20220217203847/https://www.ffjm.org/upload/fichiers/THE_PROBLEM_OF_N_NON_DOMINATING_part_II.pdf">Placing n non dominating queens on the n X n chessboard. Part II</a>, French Federation of Mathematical Games.
%F A274947 T(n,1) = 3*n-2 for n >= 1.
%e A274947 The triangle begins:
%e A274947 0
%e A274947 0, 1,
%e A274947 0, 4, 4, 4, 4,
%e A274947 0, 7, 8, 9, 9, 9, 9, 9, 9, 9,
%e A274947 0, 10, 13, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
%e A274947 0, 13, 18, 20, 21, 22, 23, 23, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
%e A274947 0, 16, 23, 27, 28, 30, 31, 32, 32, 33, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
%e A274947 0, 19, 28, 33, 33, 38, 39, 42, 43, 43, 43, 44, 45, 45, 45, 45, 45, 47, 47, 47, 47, 47, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49,
%e A274947 0, 22, 33, 39, 40, 47, 49, 51, 53, 54, 55, 56, 57, 57, 58, 58, 59, 59, 60, 60, 60, 60, 60, 60, 60, 61, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
%e A274947 0, 25, 38, 45, 45, 54, 57, 61, 62, 63, 67, 68, 69, 70, 71, 72, 72, 72, 72, 73, 74, 75, 75, 75, 75, 76, 76, 76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 79, 79, 79, 79, 79, 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81,
%e A274947 0, 28, 43, 51, 52, 63, 67, 70, 74, 76, 78, 81, 82, 84, 85, 86, 87, 88, 88, 89, 90, 90, 90, 91, 91, 92, 92, 93, 93, 93, 93, 94, 94, 94, 95, 95, 95, 95, 96, 96, 96, 96, 96, 96, 96, 96, 96, 96, 96, 97, 98, 98, 98, 98, 98, 98, 98, 98, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
%e A274947 ...
%e A274947 (Rows 6 through 10 from _Rob Pratt_, Aug 02 2016)
%e A274947 The entry T(4,3) = 14 is achieved by
%e A274947 OXOX
%e A274947 OOOX
%e A274947 AOOO
%e A274947 OOAO
%e A274947 since the two squares marked A are not attacked by the three queens at X.
%Y A274947 Cf. A001366, A274948, A250000.
%Y A274947 Cf. A075458 (minimal number of queens needed to attack all the squares of an n X n board).
%Y A274947 Row 8 subtracted from 64 is A342151.
%K A274947 nonn,tabf
%O A274947 0,5
%A A274947 _N. J. A. Sloane_, Jul 27 2016
%E A274947 Corrections and more terms from _Andrey Zabolotskiy_, Jul 29 2016
%E A274947 More terms via integer linear programming from _Rob Pratt_, Aug 02 2016