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

DOI: 10.4236/ojdm.2013.33027   PDF   HTML   XML   5,543 Downloads   8,371 Views   Citations

Abstract

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 28k – 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 14k2 6k + 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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

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