login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006075 Minimal number of knights needed to cover an n X n board.
(Formerly M3224)
11

%I M3224

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

%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 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.

%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) = 62 added from the Context Center web site by _N. J. A. Sloane_, Mar 02 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 29 21:59 EDT 2020. Contains 337432 sequences. (Running on oeis4.)