A375116 Maximum number of squares covered (i.e., attacked) by 3 independent (i.e., nonattacking) queens on an n X n chessboard.

16, 25, 35, 45, 55, 66, 77, 88, 101, 112, 125, 136, 149, 160, 173, 184, 197, 208, 221, 232, 245, 256, 269, 280, 293, 304, 317, 328, 341, 352, 365, 376, 389, 400, 413, 424, 437, 448, 461, 472, 485, 496, 509, 520, 533, 544, 557, 568, 581, 592, 605, 616, 629, 640, 653, 664, 677

Offset

4,1

Comments

It is not possible to place 3 independent queens on a 1 X 1 or 2 X 2 or 3 X 3 board.

There is a related sequence of 'uncovered' squares i.e., n^2 - a(n).

There is another sequence denoting the potency of the new queen a(n) - A374933(n).

Links

Andrew Howroyd, Table of n, a(n) for n = 4..1000

Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Formula

a(n) = 12*n - 43 - (n mod 2) for n >= 10.

G.f.: x^4*(16 + 9*x - 6*x^2 + x^3 + x^5 + x^6 + 2*x^8)/((1 - x)^2*(1 + x)). - Andrew Howroyd, Nov 13 2025

Example

4 X 4 complete coverage with 3 queens
  x x x x
  x Q x x
  x x x Q
  Q x x x
5 X 5 complete coverage with 3 queens
  Q x x x x
  x x x x x
  x x x Q x
  x x x x x
  x x Q x x
6 X 6 incomplete 1 o/s
  x x x x o x
  Q x x x x x
  x x x x x Q
  x x x x x x
  x x Q x x x
  x x x x x x
6 X 6 coverage complete but NOT independent
  Q x x x x x
  x x x x x x
  x x x x q x
  x x x x x x
  x x q x x x
  x x x x x x
7 X 7 best leaves 4 o/s  (same layout as 6 X 6 with extra row and column)
There are alternative layouts - how many is not identified.
  x x x x o x x
  Q x x x x x x
  x x x x x Q x
  x x x x x x x
  x x Q x x x x
  x x x x x x o
  x x x o x x o

Mathematica

LinearRecurrence[{1, 1, -1}, {16, 25, 35, 45, 55, 66, 77, 88, 101}, 60] (* Paolo Xausa, Jan 18 2026 *)

Prog

(PARI) a(n) = 12*n - 43 - (n % 2) + if(n<10, [11, 9, 6, 5, 2, 2][n-3]) \\ Andrew Howroyd, Nov 13 2025

Crossrefs

Column 3 of A376732.

Cf. A047461 (for one queen), A374933 (for two queens), A374934, A374935, A374936.

Sequence in context: A176512 A001033 A100647 * A374934 A245371 A235717

Adjacent sequences: A375113 A375114 A375115 * A375117 A375118 A375119

Keyword

nonn,easy

Author

John King, Jul 30 2024

Extensions

a(6)-a(8) corrected by John King, Sep 17 2024

a(9) corrected using data from Mia Muessig by Andrew Howroyd, Oct 05 2024

Status

approved