On the Solution of the Towers of Hanoi Problem

Authors: Hayedeh Ahrabian, Comfar Badamchi, Abbass Nowzari-Dalini

Abstract:

In this paper, two versions of an iterative loopless algorithm for the classical towers of Hanoi problem with O(1) storage complexity and O(2n) time complexity are presented. Based on this algorithm the number of different moves in each of pegs with its direction is formulated.

Keywords: Loopless algorithm, Binary tree, Towers of Hanoi.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076656

References:

[1] M. D. Atkinson, The cyclic towers of Hanoi, Inform. Process. Lett. 13 (1981), 118-119.
[2] P. Buneman and L. Levy, The towers of Hanoi problem, Inform. Process. Lett. 10 (1980), 243-244.
[3] X. Chen and J. Shen, On the Frame-Stewart conjecture about the towers of Hanoi, SIAM J. Comput. 33 (2004), 584-589.
[4] H. Dudeney, The Canterbury Puzzles, Thomas Nelson & Sons, London, 1907.
[5] E. W. Dijkstra, A Short Introduction to the Art of Programming, Technisch Hogeschool Eindhoven, EWD 316, 1971.
[6] M. C. Er, A linear space algorithm for the towers of Hanoi problem by using a virtual disc, Inform. Sci. 47 (1989), 47-52.
[7] M. C. Er, A loopless and optimal algorithm for the cycle for Hanoi problem, Inform. Sci. 42 (1987), 283-287.
[8] M. C. Er, A loopless approach for constructing a fastest algorithm for the towers of Hanoi problem, Intern. J. Comput. Math. 20 (1986), 49-54.
[9] M. C. Er, The towers of Hanoi and binary numerals, J. Inform. Optim. Sci. 6 (1985), 147-152.
[10] J. S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941), 216-217.
[11] T. D. Gedeon, The cyclic towers of Hanoi: An iterative solution produced by transformation, Copmut. J. 39 (1996), 353-356.
[12] P. Gupta, P. P. chakrabarti, and S. Ghose, The towers of Hanoi: Generalizations, specializations and algorithms, Intern. J. Comput. Math. 46 (1992), 149-161.
[13] P. J. Hayes, A note on the towers of Hanoi problem, Copmut. J. 20 (1977), 282-285.
[14] S. Klavˆzar, U. Milutinovi'c, and C. Petr, On the Frame-Stewart algorithm for the multi-peg towers of Hanoi problem, Discrete Appl. Math. 120 (2002), 141-157.
[15] S. Klavˆzar and U. Milutinovi'c, Simple Explicit Formulas for the Frame- Stewart Numbers, Ann. Comb. 6 (2002), 157-167
[16] H. Mayer and D. Perkins, Towers of Hanoi revisited, SIGPLAN Notices 19 (1984), 80-84.
[17] S. Maziar, Solution of the tower of Hanoi problem using a binary tree, SIGPLAN Notice 20 (1985), 16-20.
[18] B. Meyer, A note on iterative Hanoi, SIGPLAN Notices 19 (1984), 123- 126.
[19] P. H. Schoute, De ringen van brahma, Eigen Harrd 22 (1884), 274-276.
[20] M. Sniedovich, OR/MS games: 2. Towers of Hanoi, INFORMS Transcations on Education 3 (2002), 34.
[21] B. M. Stewart, Advanced problem 3918, Amer. Math. Monthly 46 (1939), 363-363.
[22] B. M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941), 217-219.
[23] P. K. Stockmeyer, C. D. Bateman, J. W. Clark, C. R. Eyster, M. T. Harrison, N. A. Loehr, P. J. Rodriguez, and J. R. Simmons, Exchanging disks in the tower of Hanoi, Intern. J. Comput. Math. 59 (1995), 37-47.
[24] M. Saegedy, In how many steps the k peg version of the towers of Hanoi game can be solved, Lec. Note. Comput. Sci. 1563 (1999) 356-361.
[25] T. R. Walsh, The towers of Hanoi revisited: Moving the rings by counting the moves, Inform. Process. Lett. 15 (1982), 64-67.
[26] L. Xue-miao, A loopless approach to the multipeg towers of Hanoi, Intern. J. Comput. Math. 33 (1990) 13-29.