An Efficient Implementation of Tower of Hanoi using Gray Codes
Hari Krishnan.V, Meenakshi Sundararajan Engineering College Chennai, India; Sandhya.M.K ,Meenakshi Sundararajan Engineering College Chennai, India; Monica Jenefer.B ,Meenakshi Sundararajan Engineering College Chennai, India
Tower of Hanoi; Gray Codes; Recursion; Non-recursive algorithm
The Tower of Hanoi Puzzle finds its applications ranging from robotics to psychological research. This puzzle is a classic case of recursive algorithm in programming. However, this puzzle can also be implemented using iterative programming, by using binary codes or gray codes. Various applications require an optimized solution for this puzzle. In this paper, an efficient implementation of Tower of Hanoi using Gray codes for ‘n’ disks and three rods is presented. This focuses only on minimizing storage and reducing running time as required by many applications. The proposed implementation using Gray code system consumes lesser memory and slightly reduced running time compared to the conventional recursive methodology.
-
[1] https://en.wikipedia.org/wiki/Tower_of_Hanoi
[2] http://mathworld.wolfram.com/TowerofHanoi.html
[3] Lucas, É. Récréations mathématiques, Vol. 3. Paris: Gauthier-Villars, 1891-1894. (Reprinted Albert Blanchard, 1960).
[4] Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition, Pearson Education, 2012.
[5] Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer., 150-156, May 1957.
[6] Gardner, M. "The Icosian Game and the Tower of Hanoi." Ch. 6 in Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Puzzles and Games. New York: Simon and Schuster, pp. 55-62, 1959.
[7] https://en.wikipedia.org/wiki/Tower_of_Hanoi
[8] Weisstein, Eric W. "Tower of Hanoi." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TowerofHanoi.html.
[9] R. J. Gardner and P. Gritzmann, Discrete tomography: Determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997), 2271–2295.
[10] Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 111-112, 1991
[11] Poole, D. G. "The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)." Math. Mag., 323-344, 1994.
[12] http://mathworld.wolfram.com/packages/Hanoi.m.
[13] http://library.wolfram.com/infocenter/MathSource/4861
Paper ID: GRDCF003015
Published in: Conference : National Conference on Computational Intelligence Systems (NCCIS - 2017)
Page(s): 71 - 75
Published in: Conference : National Conference on Computational Intelligence Systems (NCCIS - 2017)
Page(s): 71 - 75