Abstract
The Tower of Hanoi (TH) withm+3 pegs andn discs is a one hundred years old mathematical puzzle which is now experiencing a remarkable revival in computer science, where it has been discussed e.g. in connection with production scheduling and material handling. It is usually solved by double recursion onm andn. In this paper, a solution with the same length is provided which is recursive inm, but iterative inn, thus leading to a purely iterative algorithm for the four pegs TH, based on the well-known iterative solutions of the classical three pegs TH. These algorithms had turned out to be much more efficient than the recursive ones in studies of performance evaluations and might be of some interest in problems of sorting ordered instructions in a parallel computer. Some mathematical tools are derived or cited from literature in order to prove correctness of the algorithm.
Zusammenfassung
Der Turm von Hanoi (TH) mitm+3 Stangen undn Scheiben ist ein hundert Jahre altes mathematisches Spiel, das augenblicklich eine bemerkenswerte Wiederbelebung in der Informatik erfährt, wo es z. B. im Zusammenhang mit Produktionsplänen und Materialverwaltung diskutiert worden ist. Er wird üblicherweise durch doppelte Rekursion überm undn gelöst. In dieser Arbeit wird eine Lösung gleicher Länge vorgestellt, die rekursiv inm, aber iterativ inn ist und so zu einem rein iterativen Algorithmus für den Vier-Stangen-TH führt, aufbauend auf den wohlbekannten iterativen Lösungen des klassischen Drei-Stangen-TH. Diese Algorithmen hatten sich in Untersuchungen über Komplexitätsabschätzungen als viel leistungsfähiger erwiesen als die rekursiven und könnten von Interesse bei problemen des Sortierens angeordneter Befehle in Parallelrechnern sein. Einige mathematische Hilfsmittel werden hergeleitet oder aus der Literatur zitiert, um die Korrektheit des Algorithmus beweisen zu können.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Arsac, J.: Jeux et casse-tête à programmer. Paris: Dunod 1985.
Cull, P., Ecklund, E. F. Jr.: On the Towers of Hanoi and Generalized Towers of Hanoi Problems. Congress. Numer.35, 229–238 (1982).
Cull, P., Ecklund, E. F. Jr.: Towers of Hanoi and analysis of algorithms. Amer. Math. Monthly92, 407–420 (1985).
Dudeney, H. E.: The Canterbury Puzzles. New York: Dutton 1908.
Er, M. C.: Performance Evaluations of Recursive and Iterative Algorithms for the Towers of Hanoi Problem. Computing37, 93–102 (1986).
Hering, H.: Minimalstrategien in endlichen Systemen. Der Mathematikunterricht23/4, 19–35 (1977).
Hinz, A. M.: The Tower of Hanoi (in preparation).
Lavallée, I.: Note sur le problème des Tours de Hanoi. Rev. Roumaine Math. Pures Appl.30, 433–438 (1985).
Lucas, E.: Nouveaux jeux scientifiques de M. Edouard Lucas. La Nature17 (2e sémestre), 301–303 (1889).
Lunnon, W. F.: The Reve's Puzzle. Comput. J.29, 478 (1986).
Rohl, J. S., Gedeon, T. D.: Four-Tower Hanoi and Beyond. Austral. Comput. Sci. Comm.5, 156–162 (1983).
Rohl, J. S., Gedeon, T. D.: The Reve's Puzzle. Comput. J.29, 187–188 (1986); Corrigendum31, 190 (1988).
Roth, T.: The Tower of Brahma revisieted. J. Recreational Math.7, 116–119 (1974).
Schoute, P. H.: Die Ringen van Brahma. Eigen Haard1884, 274–276, 286–287.
Stewart, B. M.: Problem 3918. Amer. Math. Monthly46, 363 (1939).
B. M.: Solution. Amer. Math. Monthly48, 217–219 (1941).
Wood, D.: The Towers of Brahma and Hanoi revisited. J. Recreational Math.14, 17–24 (1981–82).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hinz, A.M. An iterative algorithm for the Tower of Hanoi with four pegs. Computing 42, 133–140 (1989). https://doi.org/10.1007/BF02239743
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02239743