Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T10:20:32.714Z Has data issue: false hasContentIssue false
  • English
  • Français

Generalized multi-peg tower of hanoi problem

Published online by Cambridge University Press:  17 February 2009

A. A. K. Majumdar
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper treats the multi-peg generalization of the Tower of Hanoi problem with n(≥ 1) disks and p(≥ 3) pegs, P1, P2,…, Pp. Denoting by M(n, p) the presumed minimum number of moves required to transfer the tower of n disks from the source peg, P1, to the destination peg, Pp, under the condition that each move transfers the topmost disk from one peg to another such that no disk is ever placed on top of a smaller one, the Dynamic Programming technique has been employed to find the optimality equation satisfied by M(n, p). Though an explicit expression for M(n, p) is given, no explicit expressions for the partition numbers (at which M(n, p) is attained) are available in the literature for p ≥ 5. The values of the partition numbers have been given in this paper.

Type
Research Article
Information
The ANZIAM Journal , Volume 38 , Issue 2 , October 1996 , pp. 201 - 208
Copyright
Copyright © Australian Mathematical Society 1996

References

[1]Atkinson, M. D., “The cyclic Towers of Hanoi”, Inform. Proc. Letters 13 (1981) 118–119.CrossRefGoogle Scholar
[2]Ball, W. W. R., Mathematical recreations and essays (Macmillan Book Co. Ltd., London, 1959).Google Scholar
[3]Chan, T., “A statistical analysis of the Tower of Hanoi problem”, Intrn. J. Computer Math. 28 (1989) 57–65.CrossRefGoogle Scholar
[4]Chu, I-Ping and Johnsonbaugh, R., “The four peg Tower of Hanoi puzzle”, SIGCSE Bulletin 23 (1991) 2–4.CrossRefGoogle Scholar
[5]Daum, I., Ackermann, H., Schugens, M. M., Reingold, C., Dichgans, J. and Birbaumer, N., “The cerebellum and cognitive functions in humans”, Behavioral Neuroscience 107 (1993) 411–419.CrossRefGoogle ScholarPubMed
[6]Frame, J. S., “Solution to AMM problem 3918”, Amer. Math. Monthly 48 (1941) 216–219.Google Scholar
[7]Gardner, M., Mathematical Puzzles and Diversions (Penguin Book, London, 1956).Google Scholar
[8]Hinz, A. M., “An iterative algorithm for the Tower of Hanoi with four pegs”, Computing 42 (1989) 133–140.CrossRefGoogle Scholar
[9]Hinz, A. M., “Pascal's Triangle and the Tower of Hanoi”, Amer. Math. Monthly 99 (1992) 538–544.CrossRefGoogle Scholar
[10]Hinz, A. M., “The Tower of Hanoi”, L Enseignement Math. 35 (1989) 289–321.Google Scholar
[11]Hinz, A. M., “Shortest paths between regular states of the Tower of Hanoi”, Inform Sci. 63 (1992) 173–181.CrossRefGoogle Scholar
[12]Johnsonbaugh, R., Discrete Mathematics (Macmillan, New York, 1990).Google Scholar
[13]Liefvoort, A. van de, “An iterative solution to the four–peg Tower of Hanoi problem”, Proc. CSC (1990) 70–75.Google Scholar
[14]Liefvoort, A. van de, “An iterative Algorithm for the Reve's puzzle”, Computer J. 35 (1992) 91–92.CrossRefGoogle Scholar
[15]Lunnon, W. F., “The Reve's puzzle”, Computer J. 29 (1986) 478.CrossRefGoogle Scholar
[16]Majumdar, A. A. K., “The gereralized four-peg Tower of Hanoi problem”, Optimization 29 (1994) 349–360.CrossRefGoogle Scholar
[17]Newman-Wolfe, R., “Observations on multi-peg Towers of Hanoi”, Rochester Univ. Computer Sci. Dept. Rep. 187 (1986) 1–19.Google Scholar
[18]Osato, N., “MARC: A multiagent robot control system”, Systems Comp. Japan 24 (1993) 42–51.CrossRefGoogle Scholar
[19]Papadimitriou, C. H. and Steiglitz, K., Combinatorial Optimization (Prentice-Hall, New Jersy, 1982).Google Scholar
[20]Poole, D., “The bottleneck Tower of Hanoi problem”, J. Recreational Math. 24 (1992) 203–207.Google Scholar
[21]Reingold, E. M. and Hansen, W. J., Data Structures (Little, Brown & Co., New York, 1983).Google Scholar
[22]Roberts, E., Thinking Recursively (John Wiley & Sons, New York, 1986).Google Scholar
[23]Rohl, J. S. and Gedeon, T. D., “The Reve's puzzle”, Computer J. 29 (1986) 187–188.CrossRefGoogle Scholar
[24]Roth, T., “The Tower of Brahma revisited”, J. Recreational Math. 14 (1974) 116–119.Google Scholar
[25]Schmajuk, N. A. and Thieme, A. D., “Purposive behavior and cognitive mapping- A neural network model”, Biolog. Cybern. 67 (1992) 165–172.CrossRefGoogle ScholarPubMed
[26]Sohn, A. and Gaudiot, J. L., “A connectionist approach to learning legal moves in Tower of Hanoi”, Proc. 2nd IEEE Conf. A.I. (1990) 336–371.Google Scholar
[27]Sohn, A. and Gaudiot, J. L., “Learning legal moves in planning problems- A connectionist approach”, Engg. Appl. Artf. Int. 5 (1992) 239–245.CrossRefGoogle Scholar
[28]Stewart, B. M., “Problem 3918”, Amer. Math. Monthly 46 (1939) 363.CrossRefGoogle Scholar
[29]Walsh, T. R., “The Towers of Hanoi revisited: Moving the rings by counting the moves”, Inform. Proc. Letters 15 (1982) 64–67.CrossRefGoogle Scholar
[30]Wood, D., “The Towers of Brahma and Hanoi revisited”, J. Recreational Math. 14 (1981–1982) 17–24.Google Scholar
[31]Wu, J. S. and Chen, R. J., “The Tower of Hanoi problem with parallel moves”, Inform. Proc. Letters 44 (1992) 241–243.CrossRefGoogle Scholar
[32]Wu, J. S. and Chen, R. J., “The Tower of Hanoi problems with cyclic parallel moves”, Inform. Proc. Letters 46 (1993) 1–6.CrossRefGoogle Scholar
[33]Zanten, A. J. van, “An iterative optimal algorithm for the generalized Tower of Hanoi problem”, Internl.J. Computer Math. 39 (1991) 163–168.CrossRefGoogle Scholar