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
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.
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
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.
Original entry on oeis.org
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).
Cf.
A006075 (number of solutions),
A098604 (rectangular board).
A103315 gives the total number of solutions.
a(13)-a(17) from the Morgenstern web site, Nov 08 2004
a(18) from the Morgenstern web site, Mar 20 2005
A287071
Number of dominating sets on the n X n knight graph.
Original entry on oeis.org
1, 1, 131, 29797, 13193525, 20887111133, 140629309631387, 3967227644736410265, 449972212664372225366189
Offset: 1
A002568
Number of different ways one can attack all squares on an n X n chessboard with the smallest number of non-attacking queens needed.
Original entry on oeis.org
1, 4, 1, 16, 16, 120, 8, 728, 92, 8, 2, 840, 24, 436, 10188, 128, 12, 224, 8424, 312, 72, 192, 8784, 368, 56, 224, 14500, 280, 10880, 240
Offset: 1
a(5) = 16 because it is impossible to attack all squares with 2 queens but with 3 queens you can do it in 16 different ways (with mirroring and rotation).
- W. Ahrens, Mathematische Unterhaltungen und Spiele, second edition (1910), Vol. 1, p. 301.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Mia Müßig, Julia code to compute the sequence
- M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 49.
- M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 49. [Incomplete annotated scan of title page and pages 18-51]
See
A002567 for the number of non-isomorphic solutions.
A286882
Number of minimal dominating sets in the n X n knight graph.
Original entry on oeis.org
1, 1, 14, 243, 2686, 161458
Offset: 1
A110216
Total number of coverings of a cubic board with the minimal number of knights.
Original entry on oeis.org
1, 1, 12, 156, 888
Offset: 1
Nikolaus Meyberg (Nikolaus.Meyberg(AT)t-online.de), Jul 17 2005
a(3) = 12, since reflections or rotations of
OOO KKK OOO
OKO OKO OKO
OOO OOO OOO generate twelve different coverings.
This sequence is a 3-dimensional analog of
A103315. a(n) =
A110219(n, n, n).
A102215 gives the number of inequivalent solutions.
A110219
Cone C(n,m,k) read by planes and rows, for 1 <= k <= m <= n: Total Number of 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, 4, 36, 8, 12, 12, 1, 16, 1296, 15, 56, 14, 9, 16, 8, 156, 1, 4, 2916, 6, 24, 8, 3, 4, 2, 6, 47, 2, 8, 38, 888, 1, 1, 6561, 2, 236, 2, 1, 268, 1, 2988, 46, 4, 27, 7
Offset: 1
Nikolaus Meyberg (Nikolaus.Meyberg(AT)t-online.de), Jul 17 2005
Cone starts:
1.1...1........1..............1.................1......................
..1,1.4,36....16,1296.........4,2916............1,6561.
......8,12,12.15,..56,14......6,..24,8..........2,.236,.2
...............9,..16,.8,156..3,...4,2,.6.......1,.268,.1,2988
.............................47,...2,8,38,888..46,...4,27,...7,.?
..............................................127,..32,12,...?,....
A323549
Number of minimum total dominating sets in the n X n knight graph.
Original entry on oeis.org
0, 0, 0, 36, 480, 36, 10, 16, 84, 2704, 46736, 324, 80, 4, 19776, 144
Offset: 1
Showing 1-8 of 8 results.
Comments