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

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

Cite this paper

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.

A. Miller and D. Farnsworth, "Counting the Number of Squares Reachable in k Knight’s Moves,"

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

[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