The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 4
 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, 16, 16, 16, 16, 16, 16, 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, 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,5 COMMENTS Place k queens on an n X n board so that the total number of squares attacked/occupied by the queens is minimized. 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. Entries T(n,n) are given in A001366. 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 LINKS Bernard Lemaire, Pavel Vitushinkiy, Placing n non dominating queens on the n X n chessboard. Part I, French Federation of Mathematical Games Bernard Lemaire, Pavel Vitushinkiy, Placing n non dominating queens on the n X n chessboard. Part II, French Federation of Mathematical Games FORMULA T(n,1) = 3*n-2 for n >= 1. EXAMPLE The triangle begins: 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, 16, 16, 16, 16, 16, 16, 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, 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, 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, 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, 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, 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, ... (Rows 6 through 10 from Rob Pratt, Aug 02 2016) The entry T(4,3) = 14 is achieved by OXOX OOOX AOOO OOAO since the two squares marked A are not attacked by the three queens at X. CROSSREFS Cf. A001366, A274948, A250000. Cf. A075458 (minimal number of queens needed to attack all the squares of an n X n board). Sequence in context: A174987 A214926 A268368 * A331961 A279406 A171408 Adjacent sequences:  A274944 A274945 A274946 * A274948 A274949 A274950 KEYWORD nonn,tabf AUTHOR N. J. A. Sloane, Jul 27 2016 EXTENSIONS Corrections and more terms from Andrey Zabolotskiy, Jul 29 2016 More terms via integer linear programming from Rob Pratt, Aug 02 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 18 17:32 EDT 2021. Contains 345120 sequences. (Running on oeis4.)