Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-27T13:26:18.370Z Has data issue: false hasContentIssue false
  • English
  • Français

Leaper graphs

Published online by Cambridge University Press:  01 August 2016

Donald E. Knuth
Donald E. Knuth*
Affiliation:
Computer Science Dept, Stanford University, Stanford CA 94305, USA
Get access Rights & Permissions [Opens in a new window]

Extract

An {r, s}-leaper is a generalized knight that can jump from (x, y) to (x ± r, y ± s) or (x ± s, y ± r) on a rectangular grid. The graph of an {r, s}-leaper on an m x n board is the set of mn vertices (x, y) for 0 ≤ x < m and 0 ≤ y < n, with an edge between vertices that are one {r, s} -leaper move apart. We call x the rank and y the file of board position (x,y). George P. Jelliss raised several interesting questions about these graphs, and established some of their fundamental properties. The purpose of this paper is to characterize when the graphs are connected, for arbitrary r and s, and to determine the smallest boards with Hamiltonian circuits when s = r + 1. or r = 1. (A Hamiltonian circuit is a closed path that visits every cell exactly once.)

Type
Research Article
Information
The Mathematical Gazette , Volume 78 , Issue 483 , November 1994 , pp. 274 - 297
Copyright
Copyright © The Mathematical Association 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Édouard, Lucas, Récréations Mathématiques 4 (Paris, 1894).Google Scholar
2. Anthony, Dickins, A Guide to Fairy Chess (Richmond, Surrey: The Q Press, 1967).Google Scholar
3. Nash-Williams, C.St J.A., “Abelian groups, graphs and generalized knights,” Proceedings of the Cambridge Philosophical Society 55 (1959), 232–238.Google Scholar
4. Jelliss, George P., “Theory of leapers,” Chessics 2, number 24 (Winter 1985), 86–98.Google Scholar
5. Jelliss, George P., “Generalized knights and Hamiltonian tours,” preprint dated 3 September 1993.Google Scholar
6. Dawson, T.R., problem in L’Echiquier (Brussels), 1928, pages 985 and 1054.Google Scholar
7. Frolow, M., Les Carrés Magiques (Paris, 1886).Google Scholar
8. Jelliss, G.P. and Willcocks, T.H., “The five free leapers,” Chessics 1, number 2 (July 1976), 2; number 6 (August 1978), 4–5.Google Scholar
9. Euler, L., “Solution d’une question curieuse qui ne paroit soumise à aucune analyse,” Mémoires de l’Académie Royale des Sciences et Belles Letters (Berlin, 1759), 310–337.Google Scholar
10. Huber-Stockar, E., problem 6304, Fairy Chess Review 5, number 16 and 17 (1945), 124, 134.Google Scholar
11. de Jaenisch, C.F., Traité des Applications de l’Analyse Mathématique au Jeu des Echecs, St. Petersbourg, 1862–1863, volume 2.Google Scholar
12. Sainte-Marie, C. Flye, “Note sur un problème relatif à la marche du cavalier sur l’échiquier,” Bulletin de la Société Mathématique de France 5 (1877), 144–150.Google Scholar
13. Bergholt, E., Letter to the editor, The British Chess Magazine, 1918, page 74.Google Scholar
14. Jünger, Michael and Rinaldi, Giovanni, electronic communications from the University of Cologne, 29 March 1994.Google Scholar
15. Jünger, Michael, electronic communication from the University of Cologne, 8 April 1994.Google Scholar
16. Jünger, Michael, electronic communication from the University of Cologne, 11 April 1994.Google Scholar