A279402 -id:A279402 - cp's OEIS frontend

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

1, 1, 1, 2, 5, 4, 7, 6, 7, 9, 11, 10, 13, 13, 13, 14, 17, 16, 19, 18, 19, 21, 23, 22, 25, 25, 25, 26, 29, 28, 31, 30, 31, 33, 35, 34, 37, 37, 37, 38, 41, 40, 43, 42, 43, 45, 47, 46, 49, 49, 49, 50, 53, 52, 55, 54, 55, 57, 59, 58, 61, 61, 61, 62, 65, 64, 67, 66

Offset: 1

Konrad Schlude, Jul 24 2003

Independence number of the queens' graph on toroidal n X n board. - Andrey Zabolotskiy, Dec 11 2016

			Four non-attacking queens can be placed on a 6 X 6 toroidal board:
......
..Q...
....Q.
.Q....
...Q..
......
But five queens cannot. Hence a(6) = 4.

G. Polya: Über die 'Doppelt-Periodischen' Loesungen des n-Damen-Problems, in: W. Ahrens: Mathematische Unterhaltungen und Spiele, Teubner, Leipzig, 1918, 364-374. Reprinted in: G. Polya: Collected Works, Vol. V, 237-247.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Grant Cairns, Queens on Non-square Tori, El. J. Combinatorics, N6, 2001
Eldar Fischer, Tomer Kotek, and Johann A. Makowsky, Application of Logic to Combinatorial Sequences and Their Recurrence Relations
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
P. Monsky, Problem E3162, Amer. Math. Monthly 96 (1989), 258-259.
Konrad Schlude and Ernst Specker, Zum Problem der Damen auf dem Torus, Technical Report 412, Computer Science Department ETH Zurich, 2003.

Cf. A051906, A007705, A279402, A279404, A279405, A172517, A172518, A172519, A173775, A178722.

(* Explicit formula, based on an article by Monsky: *)
Table[n-1/6*(2*Cos[Pi*n/2]-3*Cos[Pi*n/3]+5*Cos[2*Pi*n/3]-Cos[Pi*n/6]-Cos[5*Pi*n/6]+3*Cos[Pi*n]+7),{n,1,100}] (* Vaclav Kotesovec, Dec 13 2010 *)

a(n)=n-1/6*(2*cos(Pi*n/2)-3*cos(Pi*n/3)+5*cos(2*Pi*n/3)-cos(Pi*n/6)-cos(5*Pi*n/6)+3*cos(Pi*n)+7);
vector(60,n,round(a(n))) \\ Joerg Arndt, Dec 13 2010

G.f.: (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/(x^13 - x^12 - x + 1) = (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/((x - 1)^2*(x + 1)*(x^2 + 1)*(x^2 - x + 1)*(x^2 + x + 1)*(x^4 - x^2 + 1)). - Joerg Arndt, Dec 13 2010
From Andrey Zabolotskiy, Dec 11 2016: (Start)
a(n) = n if n = 1, 5, 7, 11 (mod 12);
a(n) = n-1 if n = 2, 10 (mod 12);
a(n) = n-2 otherwise.
(End)

A279404 Independent domination number for queens' graph on an n X n toroidal board.

Original entry on oeis.org

1, 1, 1, 2, 5, 4, 5, 4, 5, 5, 5, 6, 7, 7, 5, 8, 9, 10

Offset: 1

Andrey Zabolotskiy, Dec 11 2016

That is, the minimal number of queens needed to cover an n X n toroidal chessboard so that every square either has a queen on it or is under attack by a queen, but not both.

A279402(n) <= a(n) <= A085801(n).

Andy Huchala, Python program.
Christina M. Mynhardt, Upper bounds for the domination numbers of toroidal queens graphs, Discussiones Mathematicae Graph Theory, 23 (2003), 163-175.

Cf. A075324, A085801, A279402.

a(3*n) = n if n = 1, 5, 7, 11 (mod 12).

a(17)-a(18) from Andy Huchala, Mar 09 2024

A279407 Domination number for knight graph on an n X n toroidal board.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 9, 8, 12, 15, 18, 21, 25, 28, 33, 32

Offset: 1

Andrey Zabolotskiy, Dec 12 2016

That is, the minimal number of knights needed to cover an n X n toroidal chessboard so that every square either has a knight on it, or is under attack by a knight, or both.

			For an 8 X 8 board, the solution is:
  N . . . . . . N
  . . . . . . . .
  . . N . . N . .
  . . . . . . . .
  . . . N N . . .
  . . . . . . . .
  . N . . . . N .
  . . . . . . . .

John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pages 140-144.

Andy Huchala, Python program.

Cf. A006075, A279402.

a(9)-a(16) from Andy Huchala, Mar 03 2024

A279408 Triangle read by rows: T(n,m) (n>=m>=1) = domination number for kings' graph on an n X m toroidal board.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 2, 2, 2, 4, 4, 2, 2, 2, 4, 4, 4, 3, 3, 3, 5, 5, 6, 7, 3, 3, 3, 6, 6, 6, 8, 8, 3, 3, 3, 6, 6, 6, 9, 9, 9, 4, 4, 4, 7, 7, 8, 10, 11, 12, 14, 4, 4, 4, 8, 8, 8, 11, 11, 12, 15, 15, 4, 4, 4, 8, 8, 8, 12, 12, 12, 16, 16, 16, 5, 5, 5, 9, 9, 10, 13, 14, 15, 18, 19, 20, 22

Offset: 1

Andrey Zabolotskiy, Dec 16 2016

That is, the minimal number of kings needed to cover an n X m toroidal chessboard so that every square has a king on it, is under attack by a king, or both.

For the usual non-toroidal case, the formula is ceiling(m/3)*ceiling(n/3).

			T(7,7)=7 can be reached by:
...K...
......K
..K....
.....K.
.K.....
....K..
K......

John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pages 144-149.

Indranil Ghosh, Rows 1..100, flattened
Dan Freeman, Chessboard Puzzles Part 4 - Other Surfaces and Variations.

Cf. A075561, A279402, A279407, A279209.

Flatten[Table[Ceiling[Max[m Ceiling[n/3], n Ceiling[m/3]]/3],{n, 1, 13}, {m, 1, n}]] (* Indranil Ghosh, Mar 09 2017 *)

T(n,m) = ceil(max(m*ceil(n/3), n*ceil(m/3))/3)
for(n=1,20,for(m=1,n, print1(T(n,m)", "))) \\ Charles R Greathouse IV, Dec 16 2016

T(n,m) = ceiling(max(m*ceiling(n/3), n*ceiling(m/3))/3).

A279403 Irregular triangle read by rows: T(n,k) (n>=1, 0 <= k <= n^2) = minimal number of squares not attacked by k queens on an n X n toroidal board, with trailing zeros truncated.

Original entry on oeis.org

1, 4, 9, 16, 4, 25, 8, 2, 36, 16, 4, 49, 24, 11, 4, 64, 36, 16, 6, 81, 48, 27, 12, 3, 100, 64, 36, 19, 4, 121, 80, 51, 29, 13, 144, 100, 64, 39, 16, 6, 169, 120, 83, 53, 29, 8, 2, 196, 144, 100, 67, 36, 18, 8, 225, 168, 223, 82, 41, 256, 196, 144, 103, 64, 40

Offset: 1

Andrey Zabolotskiy, Dec 11 2016

Row lengths are A279402.

			The triangle begins:
1 (0)
4 (0, 0, 0, 0)
9 (0, 0, ...)
16 4 (0, 0, ...)
25 8 2
36 16 4
49 24 11 4
64 36 16 6
81 48 27 12 3
100 64 36 19 4
121 80 51 29 13
144 100 64 39 16 6
169 120 83 53 29 8 2
196 144 100 67 36 18 8
225 168 123 82 41
256 196 144 103 64 40 ...

Cf. A279402, A279406.

T(n,0) = A000290(n).
T(n,1) = A000290(n)-A047461(n) = A137932(n-1).
T(n,2) = A248825(n-4) for n >= 6.

cp's OEIS Frontend

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A279404 Independent domination number for queens' graph on an n X n toroidal board.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A279407 Domination number for knight graph on an n X n toroidal board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A279408 Triangle read by rows: T(n,m) (n>=m>=1) = domination number for kings' graph on an n X m toroidal board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A279403 Irregular triangle read by rows: T(n,k) (n>=1, 0 <= k <= n^2) = minimal number of squares not attacked by k queens on an n X n toroidal board, with trailing zeros truncated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula