

A006075


Minimal number of knights needed to cover an n X n board.
(Formerly M3224)


12



1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, 40, 46, 52, 57, 62, 68
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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 annealingbased 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


REFERENCES

David C. Fisher, On the N X N Knight Cover Problem, Ars Combinatoria 69 (2003), 255274.
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, 255267.
Bernard Lemaire, Knights Covers on N X N Chessboards, J. Recreat. Math., Vol. 312, 2003, 8799.
Frank Rubin, Improved knight coverings, Ars Combinatoria 69 (2003), 185196.
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.


LINKS

Lee Morgenstern, Knight Domination. [Much material, including optimality proofs for the values given in this entry]


EXAMPLE

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


CROSSREFS

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


KEYWORD

nonn,hard,more,nice


AUTHOR



EXTENSIONS

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


STATUS

approved



