A006075 -id:A006075 - cp's OEIS frontend

A006076 Sequence A006075 gives minimal number of knights needed to cover an n X n board. This sequence gives number of inequivalent solutions using A006075(n) knights.

1, 1, 2, 3, 8, 23, 3, 1, 1, 2, 100, 1, 20, 1, 63, 1, 29, 2551

Offset: 1

David C. Fisher, On the N X N Knight Cover Problem, Ars Combinatoria 69 (2003), 255-274.
M. Gardner, Mathematical Magic Show. Random House, NY, 1978, p. 194.
Bernard Lemaire, Knights Covers on N X N Chessboards, J. Recreational Mathematics, Vol. 31-2, 2003, 87-99.
Frank Rubin, Improved knight coverings, Ars Combinatoria 69 (2003), 185-196.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Lee Morgenstern, Knight Domination.
Frank Rubin, Knight coverings for large chessboards, 2000.
Eric Weisstein's World of Mathematics, Knights Problem.

Cf. A006075 (number of solutions), A098604 (rectangular board). A103315 gives the total number of solutions.

a(11) was found in 1973 by Bernard Lemaire. (Philippe Deléham, Jan 06 2004)
a(13)-a(17) from the Morgenstern web site, Nov 08 2004
a(18) from the Morgenstern web site, Mar 20 2005

A075458 Domination number for queens' graph Q(n).

Original entry on oeis.org

1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, 11, 11, 12, 12, 13, 13

Offset: 1

N. J. A. Sloane, Oct 16 2002

From Dmitry Kamenetsky, Sep 03 2019: (Start)
Minimum number of queens needed to occupy or attack all squares of an n X n chessboard.
a(n) >= ceiling(n/2) for all n, except n = 3, 11. See paper by Finozhenok and Weakley below.
a(n) = p or p+1, where p = ceiling(n/2), proved for all n <= 132, except n = 3, 11. See paper by Ostergard and Weakley below. Note that this implies that a(n+4) > a(n). (End)

W. W. R. Ball and H. S. M. Coxeter, "Math'l Rec. and Essays," 13th Ed. Dover, p. 173.
John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), pp. 113-137

William Herbert Bird, Computational methods for domination problems, University of Victoria, 2017. See Table 5.1 on p. 114.
S. Bozóki, P. Gál, I. Marosi and W. D. Weakley, Domination of the rectangular queen's graph, arXiv:1606.02060 [math.CO], 2016.
Domingos M. Cardoso, Inês Serôdio Costa, and Rui Duarte, Spectral properties of the n-Queens' Graphs, arXiv:2012.01992 [math.CO], 2020. See p. 10.
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022.
Dmitry Finozhenok and W. Doug Weakley, An Improved Lower Bound for Domination Numbers of the Queen’s Graph, Australasian Journal of Combinatorics, vol. 37, 2007, p. 295-300.
Dmitry Kamenetsky, Best known solutions for n <= 26.
Dmitry Kamenetsky, Matlab program to compute a(n) for small n.
Dmitry Kamenetsky, Java program to compute the best known solutions.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Australasian Journal of Combinatorics 23 (2001), 253-284.
Stephan Mertens, Domination Polynomial of the Rook Graph, arXiv:2401.00716 [math.CO], 2024.
Patric R. J. Östergård and William D. Weakley, Values of Domination Numbers of the Queen's Graph, The Electronic Journal of Combinatorics, volume 8, issue 1, 2001.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 49.
A. Sinko and P. J. Slater, Queen's domination using border squares and (A,B)-restricted domination, Discrete Math., 308 (2008), 4822-4828.
Stan Wagon, Graph Theory Problems from Hexagonal and Traditional Chess, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287.
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Queen Graph
Eric Weisstein's World of Mathematics, Queens Problem

A002563 gives number of solutions.
Cf. A006075, A075561, A189889.
Cf. A075324 (independent domination number).

a(19) from Peter Karpov, Mar 01 2016

a(20)-a(24) from Bird and a(25) from Dmitry Kamenetsky's file added by Andrey Zabolotskiy, Sep 03 2021

A075561 Domination number for kings' graph K(n).

Original entry on oeis.org

1, 1, 1, 4, 4, 4, 9, 9, 9, 16, 16, 16, 25, 25, 25, 36, 36, 36, 49, 49, 49, 64, 64, 64, 81, 81, 81, 100, 100, 100, 121, 121, 121, 144, 144, 144, 169, 169, 169, 196, 196, 196, 225, 225, 225, 256, 256, 256, 289, 289, 289, 324, 324, 324, 361, 361, 361, 400, 400

Offset: 1

N. J. A. Sloane, Oct 16 2002

Also the lower independence number of the n X n knight graph. - Eric W. Weisstein, Aug 01 2023

John J. Watkins, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, 2004, p. 102.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Centre for Discrete Mathematics and Theoretical Computer Science, CDMTCS-133, May 2000.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Australasian Journal of Combinatorics 23 (2001), 253-284.
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], 2024. See p. 15.
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Kings Problem
Eric Weisstein's World of Mathematics, Lower Independence Number
Index entries for linear recurrences with constant coefficients, signature (1,0,2,-2,0,-1,1).

Cf. A189889, A075458, A006075, A102753.

Table[Floor[(n + 2)/3]^2, {n, 50}] (* Vaclav Kotesovec, May 13 2012 *)
LinearRecurrence[{1, 0, 2, -2, 0, -1, 1}, {1, 1, 1, 4, 4, 4, 9}, 20] (* Eric W. Weisstein, Jun 20 2017 *)
CoefficientList[Series[(-1 - x^3)/((-1 + x)^3 (1 + x + x^2)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 20 2017 *)

Vec(-x*(x+1)*(x^2-x+1)/((x-1)^3*(x^2+x+1)^2) + O(x^100)) \\ Colin Barker, Oct 06 2014

a(n) = floor((n+2)/3)^2. - Vaclav Kotesovec, May 13 2012
G.f.: -x*(x+1)*(x^2-x+1) / ((x-1)^3*(x^2+x+1)^2). - Colin Barker, Oct 06 2014
E.g.f.: exp(-x/2)*(exp(3*x/2)*(5 + 3*x*(3 + x)) + (6*x - 5)*cos(sqrt(3)*x/2) + sqrt(3)*(3 + 2*x)*sin(sqrt(3)*x/2))/27. - Stefano Spezia, Oct 17 2022
Sum_{n>=1} 1/a(n) = Pi^2/2 (A102753). - Amiram Eldar, Nov 03 2022

More terms added from Vaclav Kotesovec, May 13 2012

A103315 Number of minimum dominating sets for the n X n knight graph.

Original entry on oeis.org

1, 1, 8, 9, 47, 127, 10, 2, 2, 4, 800, 2, 152, 4, 504, 2, 212, 19562

Offset: 1

N. J. A. Sloane, Mar 20 2005, following a suggestion from Lee Morgenstern

In other words, as made explicit in the old name: Sequence A006075 gives minimum number of knights needed to cover an n X n board (i.e., the domination number of the n X n knight graph). This sequence (A103315) gives total number of solutions using A006075(n) knights (compare A006076).

Lee Morgenstern, Knight Domination.
Frank Rubin, Knight coverings for large chessboards, 2000.
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set

Cf. A006075 (domination number of the n X n knight graph).
Cf. A006076 (inequivalent number of minimum dominating sets).
Cf. A098604.

New name from Eric W. Weisstein, Sep 06 2021

A098604 Triangle T(n,k) read by rows, for 1 <= k <= n: minimal number of knights needed to cover a k X n board.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

How many knights are needed to occupy or attack every square of a k X n board?

I do not know how many of these numbers have been proved to be optimal. - N. J. A. Sloane, Nov 08 2004

			Triangle (with rows n >= 1 and columns k >= 1) begins as follows:
  1
  2 4
  3 4 4
  4 4 4 4
  5 4 4 4 5
  6 4 4 4 6 8
  7 6 6 6 7 8 10
  ...

Lee Morgenstern, Knight Domination.
Frank Rubin, Knight coverings for large chessboards, 2000.
Eric Weisstein's World of Mathematics, Knights Problem.

See A006075 for the n X n case (the main diagonal). A006076 gives number of ways to cover an n X n board using the minimal number of knights.

Morgenstern's table extends a long way beyond what is shown here.

A110214 Minimal number of knights to cover a cubic board.

Original entry on oeis.org

1, 8, 6, 8, 13

Offset: 1

Nikolaus Meyberg (Nikolaus.Meyberg(AT)t-online.de), Jul 17 2005

			Illustration for n = 3, 4, 5 ( O = empty field, K = knight ):
n = 3: OOO KKK OOO n = 4: OOOO OKOO OOOO OOOO
...... OKO OKO OKO ...... OOOO OKKK OOOO OOOO
...... OOO OOO OOO ...... OOOO KKKO OOOO OOOO
......................... OOOO OOKO OOOO OOOO
n = 5: 1, 2, 4 and 5 planes empty, 3 plane: OKOKO OKOKO KKKKK KOKOK OOKOO.

This is a 3-dimensional version of A006075. a(n) = A110217(n, n, n). A110215 gives number of inequivalent ways to cover the board using a(n) knights, A110216 gives total number.

Generalize a knight for a spatial board: a move consists of two steps in the first, one step in the second and no step in the third dimension. How many of such knights are needed to occupy or attack every field of an n X n X n board? Knights may attack each other.

A110217 Cone C(n,m,k) read by planes and rows, for 1 <= k <= m <= n: minimal number of knights needed to cover a k X m X n board.

Original entry on oeis.org

1, 2, 4, 8, 3, 4, 8, 4, 6, 6, 4, 4, 8, 4, 6, 6, 4, 6, 7, 8, 5, 4, 8, 4, 6, 6, 4, 6, 7, 8, 5, 6, 8, 10, 13, 6, 4, 6, 4, 7, 6, 4, 8, 8, 12, 6, 8, 10, 12

Offset: 1

Nikolaus Meyberg (Nikolaus.Meyberg(AT)t-online.de), Jul 17 2005

			Cone starts:
1..2....3......4........5............6.................
...4.8..4.8....4.8......4.8..........4..6
........4.6.6..4.6.6....4.6.6........4..7..6
...............4.6.7.8..4.6.7..8.....4..8..8.12
........................5.6.8.10.13..6..8.10.12.?
.....................................8.11.12..?....

C(n, n, 1) = A006075(n), C(n, k, 1) = A098604(n, k), C(n, n, n) = A110214(n). A110218 gives number of inequivalent ways to cover the board using C(n, m, k) knights, A110219 gives total number.

How many knights with move vector (2, 1, 0) are needed to occupy or attack every field of a k X m X n board? Knights may attack each other.

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

A261752 Minimum number of knights on an n X n chessboard such that every square is attacked.

Original entry on oeis.org

6, 7, 8, 10, 14, 18, 22, 25, 28, 32, 36, 43, 48, 54, 58, 66, 70, 78, 84, 91, 98, 107, 112, 123, 128, 139, 146, 156, 164

Offset: 4

Matthew Conroy, Aug 31 2015

Total domination number of n X n knight graph.
Distinct from A006075 since here all squares must be attacked, whereas, in A006075, all squares are either attacked or occupied.
a(34) = 182, a(36) = 202, a(38) = 224. - Andy Huchala, Jun 04 2021

			An example for the 4 X 4 case:
  ....
  .NNN
  .N..
  NN..
and for the 5 x 5 case:
  .....
  ..N..
  .NN..
  NNN..
  N....

Matthew Conroy, Examples of minimum knight arrangements, n = 4 through n = 14
Andy Huchala, Python program
Giovanni Resta, Examples of minimum knight arrangements, from n = 15 to n = 18
Andy Huchala, Examples of minimum knight arrangements, from n = 25 to n = 34
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Total Domination Number

Cf. A006075.

a(15)-a(18) from Giovanni Resta, Aug 31 2015
a(19)-a(26) from Andy Huchala, Oct 16 2017
a(27)-a(30) from Andy Huchala, Oct 18 2017
a(31)-a(32) from Andy Huchala, Jun 04 2021

A342576 Independent domination number for knight graph on an n X n board.

Original entry on oeis.org

1, 4, 4, 4, 5, 8, 13, 14, 14, 16, 22, 24, 29, 33, 36, 40, 47, 52, 58, 63, 68

Offset: 1

Andrey Zabolotskiy, Mar 15 2021

Sandra M. Hedetniemi, Stephen T. Hedetniemi, Robert Reynolds, Combinatorial Problems on Chessboards: II, in: Domination in Graphs - Advanced Topics, Marcel Dekker, 1998. See p. 141.

Andy Huchala, Python program.
Robert Israel, Optimal configurations for n = 3 to 14
Eric Weisstein's World of Mathematics, Knight Graph.
Eric Weisstein's World of Mathematics, Lower Independence Number.

Cf. A006075, A075324, A299029, A279404, A030978.

f:= proc(N)
  local verts,Rverts,edg,cons,i,j,e;
  verts:= [seq(seq([i,j],i=1..N),j=1..N)]:
  for i from 1 to N^2 do Rverts[op(verts[i])]:= i od:
  edg:= {seq(seq({Rverts[i,j],Rverts[i+1,j+2]},i=1..N-1),j=1..N-2),
       seq(seq({Rverts[i,j],Rverts[i+2,j+1]},i=1..N-2),j=1..N-1),
       seq(seq({Rverts[i,j],Rverts[i+1,j-2]},i=1..N-1),j=3..N),
       seq(seq({Rverts[i,j],Rverts[i+2,j-1]},i=1..N-2),j=2..N)}:
  cons:= {seq(x[e[1]]+x[e[2]]<=1, e=edg),
    seq(x[i]+add(`if`(member({i,j},edg),x[j],0),j=1..N^2)>=1, i=1..N^2)}:
  Optimization:-Minimize(add(x[i],i=1..N^2),cons,assume=binary)[1]
end proc:
map(f, [$1..13]); # Robert Israel, Mar 17 2021

a(11) to a(14) from Robert Israel, Mar 17 2021
a(15)-a(18) from Eric W. Weisstein, Aug 01 2023
a(19) from Eric W. Weisstein, Jan 14 2024
a(20)-a(21) from Andy Huchala, Mar 10 2024

cp's OEIS Frontend

A006076 Sequence A006075 gives minimal number of knights needed to cover an n X n board. This sequence gives number of inequivalent solutions using A006075(n) knights.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A075458 Domination number for queens' graph Q(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A075561 Domination number for kings' graph K(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A103315 Number of minimum dominating sets for the n X n knight graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A098604 Triangle T(n,k) read by rows, for 1 <= k <= n: minimal number of knights needed to cover a k X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A110214 Minimal number of knights to cover a cubic board.

Views

Author

Keywords

Examples

Crossrefs

Formula

A110217 Cone C(n,m,k) read by planes and rows, for 1 <= k <= m <= n: minimal number of knights needed to cover a k X m X n board.

Views

Author

Keywords

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A261752 Minimum number of knights on an n X n chessboard such that every square is attacked.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs