A006076 -id:A006076 - cp's OEIS frontend

A098119 Erroneous version of A006076.

Original entry on oeis.org

1, 1, 2, 3, 8, 22, 3, 1, 1, 2, 100, 1

Offset: 1

dead

A006075 Minimal number of knights needed to cover an n X n board.

Original entry on oeis.org

1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, 40, 46, 52, 57, 62, 68

Offset: 1

N. J. A. Sloane

How many knights are needed to occupy or attack every square of an n X n board?
Also known as the domination number of the n X n knight graph. - Eric W. Weisstein, May 27 2016
Upper bounds for the terms after a(20) = 62 are as follows: 68, 75, 82, 88, 96, 102, ... (see Frank Rubin's web site).
The value a(15) = 37 given by Jackson and Pargas is wrong. A simulated annealing-based program I wrote found several complete coverages of a 15 X 15 board with 36 knights. - John Danaher (jsd(AT)mit.edu), Oct 24 2000

			Illustrations for a(3) = 4, a(4) = 4, a(5) = 5 (o = empty square, X = knight):
ooo .. oooo .. ooooo
oXo .. oXXo .. ooXoo
XXX .. oXXo .. oXXXo
...... oooo .. ooXoo
.............. ooooo

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.
Anderson H. Jackson and Roy P. Pargas, Solutions to the N x N Knights Cover Problem, J. Recreat. Math., Vol. 23(4), 1991, 255-267.
Bernard Lemaire, Knights Covers on N X N Chessboards, J. Recreat. Math., 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).
John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), p. 97.

J. Danaher, Results for 15 X 15 board.
Andy Huchala, Python program.
Lee Morgenstern, Knight Domination. [Much material, including optimality proofs for the values given in this entry]
Frank Rubin, Contest Center Web Site, Knight Coverings for Large Chessboards. [Much material, including many illustrations]
Frank Rubin, Illustration of three 52-knight coverings of an 18 X 18 board. (see Frank Rubin's web site, from which this is taken, for many further examples)
Eric Weisstein's World of Mathematics, Domination Number.
Eric Weisstein's World of Mathematics, Knight Graph.
Eric Weisstein's World of Mathematics, Knights Problem.

A006076 gives number of inequivalent ways to cover the board using a(n) knights, A103315 gives total number.

Cf. A075458, A075561, A189889, A342576.

Terms (or bounds) through a(26) updated by Frank Rubin (contestcen(AT)aol.com), May 22 2002
a(20) added from the Contest Center web site by N. J. A. Sloane, Mar 02 2006
a(21) added by Andy Huchala, Jun 06 2021

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.

A110218 Cone C(n,m,k) read by planes and rows, for 1 <= k <= m <= n: Number of inequivalent coverings of a k X m X n board using A110217(n,m,k) knights.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 6, 2, 3, 1, 1, 7, 103, 6, 10, 3, 3, 2, 1, 8, 1, 2, 196, 2, 5, 2, 2, 1, 1, 3, 8, 1, 2, 8, 37, 1, 1, 451, 1, 33, 1, 1, 55, 1, 220, 16, 3, 12, 5

Offset: 1

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

			Cone starts:
1..1.....1........1.............1..................1........................
...1,.1..2,.6.....7,.103........2,.196.............1,.451
.........2,.3,.1..6,..10,.3.....2,...5,.2..........1,..33,..1
..................3,...2,.1,.8..2,...1,.1,.3.......1,..55,..1,.220
................................8,...1,.2,.8,.37..16,...3,.12,...5,.?
..................................................23,...2,..4,...?,....

C(n, n, 1) = A006076(n), C(n, n, n) = A110215(n). A110219 gives total number of solutions.

A110215 Inequivalent coverings of a cubic board with the minimal number of knights.

Original entry on oeis.org

1, 1, 1, 8, 37

Offset: 1

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

This sequence is a 3-dimensional analog of A006076.

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

			a(3) = 1, since up to rotations and reflections,
OOO KKK OOO
OKO OKO OKO
OOO OOO OOO is the only covering for n = 3.

Cf. A006076, A110214, A110218.

A110216 gives total number of solutions.

a(n) = A110218(n, n, n).

cp's OEIS Frontend

A098119 Erroneous version of A006076.

Views

Author

Keywords

A006075 Minimal number of knights needed to cover an n X n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

A110218 Cone C(n,m,k) read by planes and rows, for 1 <= k <= m <= n: Number of inequivalent coverings of a k X m X n board using A110217(n,m,k) knights.

Views

Author

Keywords

Examples

Crossrefs

A110215 Inequivalent coverings of a cubic board with the minimal number of knights.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula