login
This site is supported by donations to The OEIS 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
1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, 40, 46, 52, 57, 62 (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: 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. 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).

John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), p. 97

LINKS

Table of n, a(n) for n=1..20.

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, Domination Number

Eric Weisstein's World of Mathematics, Knight Graph

Eric Weisstein's World of Mathematics, Knights Problem

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.

Cf. A075458, A075561, A189889.

Sequence in context: A036858 A131957 A127932 * A241295 A074904 A010304

Adjacent sequences:  A006072 A006073 A006074 * A006076 A006077 A006078

KEYWORD

nonn,hard,more,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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, Mar 02 2006

STATUS

approved

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 May 23 03:04 EDT 2019. Contains 323507 sequences. (Running on oeis4.)