OJDM  Vol.3 No.3 , July 2013
Counting the Number of Squares Reachable in k Knight’s Moves

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.

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