|
%I M3224 #60 Jun 07 2021 04:47:11
%S 1,4,4,4,5,8,10,12,14,16,21,24,28,32,36,40,46,52,57,62,68
%N Minimal number of knights needed to cover an n X n board.
%C How many knights are needed to occupy or attack every square of an n X n board?
%C Also known as the domination number of the n X n knight graph. - _Eric W. Weisstein_, May 27 2016
%C Upper bounds for the terms after a(20) = 62 are as follows: 68, 75, 82, 88, 96, 102, ... (see Frank Rubin's web site).
%C 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
%D David C. Fisher, On the N X N Knight Cover Problem, Ars Combinatoria 69 (2003), 255-274.
%D M. Gardner, Mathematical Magic Show. Random House, NY, 1978, p. 194.
%D 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.
%D Bernard Lemaire, Knights Covers on N X N Chessboards, J. Recreat. Math., Vol. 31-2, 2003, 87-99.
%D Frank Rubin, Improved knight coverings, Ars Combinatoria 69 (2003), 185-196.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), p. 97.
%H J. Danaher, <a href="/A006075/a006075.txt">Results for 15 X 15 board</a>.
%H Andy Huchala, <a href="/A006075/a006075.py3.txt">Python program</a>.
%H Lee Morgenstern, <a href="https://web.archive.org/web/20070102070601/http://home.earthlink.net/~morgenstern/">Knight Domination</a>. [Much material, including optimality proofs for the values given in this entry]
%H Frank Rubin, Contest Center Web Site, <a href="http://www.contestcen.com/knight.htm">Knight Coverings for Large Chessboards</a>. [Much material, including many illustrations]
%H Frank Rubin, <a href="/A006075/a006075a.html">Illustration of three 52-knight coverings of an 18 X 18 board</a>. (see Frank Rubin's web site, from which this is taken, for many further examples)
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominationNumber.html">Domination Number</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KnightsProblem.html">Knights Problem</a>.
%e Illustrations for a(3) = 4, a(4) = 4, a(5) = 5 (o = empty square, X = knight):
%e ooo .. oooo .. ooooo
%e oXo .. oXXo .. ooXoo
%e XXX .. oXXo .. oXXXo
%e ...... oooo .. ooXoo
%e .............. ooooo
%Y A006076 gives number of inequivalent ways to cover the board using a(n) knights, A103315 gives total number.
%Y Cf. A075458, A075561, A189889, A342576.
%K nonn,hard,more,nice
%O 1,2
%A _N. J. A. Sloane_
%E Terms (or bounds) through a(26) updated by Frank Rubin (contestcen(AT)aol.com), May 22 2002
%E a(20) added from the Contest Center web site by _N. J. A. Sloane_, Mar 02 2006
%E a(21) added by _Andy Huchala_, Jun 06 2021
|
