Counting the Number of Squares Reachable in k Knight’s Moves ()

Amanda M. Miller, David L. Farnsworth

School of Mathematical Sciences, Rochester Institute of Technology, Rochester, USA.

**DOI: **10.4236/ojdm.2013.33027
PDF
HTML XML
7,424
Downloads
12,356
Views
Citations

School of Mathematical Sciences, Rochester Institute of Technology, Rochester, USA.

Using
geometric techniques, formulas for the number of squares that require* k* moves in order to be reached by a
sole knight from its initial position on an infinite
chessboard are derived. The number of squares reachable in exactly* k* moves are 1, 8, 32, 68, and 96 for *k* = 0, 1, 2, 3, and 4, respectively, and
28*k* – 20 for *k *≥ 5. The cumulative number of squares reachable in *k* or fever moves are 1, 9, 41, and 109 for *k* = 0, 1, 2, and 3, respectively, and 14*k*^{2} – 6*k* + 5 for *k* ≥ 4. Although these formulas are known, the proofs that are presented are new and more
mathematically accessible then preceding proofs.

Share and Cite:

A. Miller and D. Farnsworth, "Counting the Number of Squares Reachable in k Knight’s Moves," *Open Journal of Discrete Mathematics*, Vol. 3 No. 3, 2013, pp. 151-154. doi: 10.4236/ojdm.2013.33027.

1. Introduction

Besides the game of chess, applications of knight’s moves include creating magic squares [1,2, pp. 53-63], recognizing patterns [3], identifying chemically similar elements in the periodic table [4,5, pp. 272-275, 325], and digital distance measurement [3,6,7].

We obtain formulas for the number of squares reachable by a knight on an infinite chessboard in a minimum of k moves and for the cumulative number of squares that the knight can reach in k moves. Our arguments are mainly geometric and have the advantage of being relatively elementary. These formulas are known, but our proofs are new and more mathematically accessible then currently available proofs, which are referenced in Section 3.

The knight moves in a way that is much different from the other chess pieces. A valid move is two squares left, right, up, or down, followed by one square in a direction perpendicular to the two squares. The eight squares that are available in one move to the knight K are indicated with 1s in Figure 1. Coordinates can be imposed on the infinite chessboard. Let r be the row coordinate and c be the column coordinate of the squares. The coordinates are integers. Each knight’s move consists of adding or subtracting 2 from one coordinate and adding or subtracting 1 from the other coordinate. The knight is initially at.

By coloring the squares alternatively white and black, starting with black in, parity arguments can be made, since a knight always moves to a square of a color different from the color of the square upon which it resides. For a knight initially at, if r + c is even, then the square is black and the square’s value of k is even. If r + c is odd, then the square is white and the square’s value of k is odd.

Figure 2 contains rows and columns –12 to 12 of the infinite chessboard. The entries are the minimum number of knight’s moves that are required by the knight K to reach each square. The numbers were obtained by counting and are easily checked. In addition to the symmetries with respect to row 0 and to column 0, the two main diagonals are lines of symmetry on the whole board. The shading of the squares in Figure 2 is used in Section 2.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | B. A. Balof and J. J. Watkins, “Knight’s Tours and Magic Squares,” Congressus Numerantium, Vol. 120, No. 1, 1996, pp. 23-32. |

[2] | J. J. Watkins, “Across the Board: The Mathematics of Chessboard Problems,” Princeton University Press, Princeton, 2004. |

[3] | P. P. Das and B. N. Chatterji, “Knight’s Distance in Digital Geometry,” Pattern Recognition Letters, Vol. 7, No. 4, 1988, pp. 215-226. doi:10.1016/0167-8655(88)90105-5 |

[4] | W. M. Hexana and N. J. Coville, “Indium as a Chemical Promoter in Fe-Based Fischer-Tropsch Synthesis,” Applied Catalysis A: General, Vol. 377, No. 1, 2010, pp. 150-157. doi:10.1016/j.apcata.2010.01.031 |

[5] | E. R. Scerri, “The Periodic Table: Its Story and Its Significance,” Oxford University Press, Oxford, 2007. |

[6] | P. P. Das, “An Algorithm for Computing the Number of the Minimal Paths in Digital Images,” Pattern Recognition Letters, Vol. 9, No. 2, 1989, pp. 107-116. doi:10.1016/0167-8655(89)90043-3 |

[7] | J. Mukherjee, P. P. Das, M. Aswatha Kumar and B. N. Chatterji, “On Approximating Euclidean Metrics by Digital Distances in 2D and 3D,” Pattern Recognition Letters, Vol. 21, No. 6-7, 2000, pp. 573-582. doi:10.1016/S0167-8655(00)00022-2 |

[8] | M. Katzman, “Counting Monomials,” Journal Algebraic Combinatorics, Vol. 22, No. 3, 2005, pp. 331-341. doi:10.1007/s10801-005-4531-6 |

[9] | N. J. A. Sloane, “On-Line Encyclopedia of Integer Sequences,” 2013. http://www.oeis.org |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.