Proving the existence of Euclidean knight’s tours on n × n × ⋯ × n chessboards for n < 4

Marco Ripà
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 30, 2024, Number 1, Pages 20–33
DOI: 10.7546/nntdm.2024.30.1.20-33
Full paper (PDF, 1613 Kb)

Details

Authors and affiliations

Marco Ripà
World Intelligence Network
Rome, Italy

Abstract

The Knight’s Tour problem consists of finding a Hamiltonian path for the knight on a given set of points so that the knight can visit exactly once every vertex of the mentioned set. In the present, we provide a 5-dimensional alternative to the well-known statement that it is not ever possible for a knight to visit once every vertex of C(3,k):=\{\underbrace{\{0,1,2\} \times \{0,1,2\}\times \cdots \times \{0,1,2\}}_\textrm{\textit{k}-times}\} by performing a sequence of 3^k-1 jumps of standard length, since the most accurate answer to the original question actually depends on which mathematical assumptions we are making at the beginning of the game when we decide to extend a planar chess piece to the third dimension and above.
Our counterintuitive outcome follows from the observation that we can alternatively define a 2D knight as a piece that moves from one square to another on the chessboard by covering a fixed Euclidean distance of \sqrt{5} so that also the statement of Theorem 3 in [Erde, J., Golénia, B., & Golénia, S. (2012), The closed knight tour problem in higher dimensions, The Electronic Journal of Combinatorics, 19(4), #P9] does not hold anymore for such a Euclidean knight, as long as a 2 × 2 × ⋯ × 2 chessboard with at least 27 cells is given. Moreover, we construct a classical closed knight’s tour on C(3,4)-\{(1,1,1,1)\} whose arrival is at a distance of 2 from (1,1,1,1), and then we show a closed Euclidean knight’s tour on \{\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\}\subseteq \mathbb{Z}^7.

Keywords

  • Knight’s tour
  • Euclidean distance
  • Knight metric
  • Hamiltonian path

2020 Mathematics Subject Classification

  • 05C12
  • 05C38
  • 05C57

References

  1. Bai, S., Yang, X.-F., Zhu, G.-B., Jiang, D.-L., & Huang, J. (2010). Generalized knight’s tour on 3D chessboards. Discrete Applied Mathematics, 158(16), 1727–1731.
  2. Cancela, H., & Mordecki, E. (2015). On the number of open knight’s tours. arXiv.org, Available online at: https://arxiv.org/abs/1507.03642.
  3. Chia, G. L., & Ong, S.-H. (2005). Generalized knight’s tours on rectangular chessboards. Discrete Applied Mathematics, 150, 80–89.
  4. DeMaio, J. (2007). Which chessboards have a closed knight’s tour within the cube? The Electronic Journal of Combinatorics, 14(1), Article #R32.
  5. DeMaio, J., & Hippchen, T. (2009). Closed knight’s tours with minimum square removal for all rectangular boards. Mathematic Magazine, 82(3), 219–225.
  6. Erde, J., Golénia, B., & Golénia, S. (2012). The closed knight tour problem in higher dimensions. The Electronic Journal of Combinatorics, 19(4), Article #P9.
  7. Euler, L. (1759). Solution d’une question curieuse que ne paroit soumise a aucune analyse. Mémoires de l’Académie (royale) des sciences de l’Institut (imperial) de France, 15, 310–337.
  8. FIDE (2022). FIDE Handbook E/01 – Laws of Chess. FIDE.com, Available online at: https://www.fide.com/FIDE/handbook/LawsOfChess.pdf.
  9. Gardner, M. (1967). Mathematical games: problems that are built on the knight’s move in chess. Scientific American, 217, 128–132.
  10. Kemp, A. (2018). Generalizing and Transferring Mathematical Definitions from Euclidean to Taxicab Geometry. Dissertation, Georgia State University. Available online at: https://scholarworks.gsu.edu/math_diss/58/.
  11. Kumar, A. (2012). Magic knight’s tours in higher dimensions. arXiv.org, Available online at: https://arxiv.org/abs/1201.0458.
  12. Miller, A. M., & Farnsworth D. L. (2013). Knight’s tours on 3×n chessboards with a single square removed. Open Journal of Discrete Mathematics, 3, 56–59.
  13. Qing, Y., & Watkins, J. J. (2006). Knight’s tours for cubes and boxes. Congressus
    Numerantium, 181, 41–48.
  14. Ripà, M. (2021). Reducing the clockwise-algorithm to k length classes. Journal of Fundamental Mathematics and Applications, 4(1), 61–68.
  15. Ripà, M. (2023). Metric spaces in chess and international chess pieces graph diameters. arXiv.org. Available online at: https://arxiv.org/abs/2311.00016.
  16. Schwenk, A. J. (1991). Which rectangular chessboards have a knight’s tour? Mathematic Magazine, 64(5), 325–332.
  17. Thompson, K. P. (2011). The nature of length, area, and volume in taxicab geometry. arXiv.org. Available online at: https://arxiv.org/abs/1101.2922.
  18. Watkins, J. J. (2004). Across the Board: The Mathematics of Chessboard Problems. Princeton University Press, Princeton, NJ.

Manuscript history

  • Received: 5 September 2023
  • Revised: 10 January 2024
  • Accepted: 24 February 2024
  • Online First: 26 February 2024

Copyright information

Ⓒ 2024 by the Author.
This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).

Related paper

Cite this paper

Ripà, M. (2024). Proving the existence of Euclidean knight’s tours on n × n × ⋯ × n chessboards for n < 4. Notes on Number Theory and Discrete Mathematics, 30(1), 20-33, DOI: 10.7546/nntdm.2024.30.1.20-33.

Comments are closed.