|
Search: id:A006075
|
|
|
| A006075 |
|
Minimal number of knights needed to cover an n X n board.
(Formerly M3224)
|
|
+0
6
|
|
| 1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, 40, 46, 52, 57, 62
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
How many knights are needed to occupy or attack every square of an n X n board?
Upper bounds for the terms after a(20) = 62 are: 68, 75, 82, 88, 96, 102, ... (see Frank Rubin's web site).
|
|
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. Rec. Math., Vol. 23 #4, pp. 255-267, 1991
Bernard Lemaire, Knights Covers on N X N Chessboards, J.Recreational Mathematics, Vol. 31-2, pp. 87-99, 2003.
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).
|
|
LINKS
|
J. Danaher, Results for 15 X 15 board
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, Link to a section of The World of Mathematics (1).
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).
|
|
EXAMPLE
|
Illustrations for a(3) = 4, a(4) = 4, a(5) = 5 (o = empty square, X = knight):
ooo .. oooo .. ooooo
oXo .. oXXo .. ooKoo
XXX .. oXXo .. oKKKo
...... oooo .. ooKoo
.............. ooooo
|
|
CROSSREFS
|
A006076 gives number of inequivalent ways to cover the board using a(n) knights, A103315 gives total number.
Adjacent sequences: A006072 A006073 A006074 this_sequence A006076 A006077 A006078
Sequence in context: A036858 A131957 A127932 this_sequence A074904 A010304 A164821
|
|
KEYWORD
|
nonn,hard,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
Comment from John Danaher (jsd(AT)mit.edu), Oct 24 2000: 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.
Terms (or bounds) through a(26) updated by Frank Rubin (contestcen(AT)aol.com), May 22 2002
a(20) = 62 added from the Context Center web site by N. J. A. Sloane (njas(AT)research.att.com), Mar 02 2006
|
|
|
Search completed in 0.002 seconds
|
