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