On an infinite family of solvable Hanoi graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On an infinite family of solvable Hanoi graphs

Full text

Pdf (222 KB)

Source

ACM Transactions on Algorithms (TALG) archive
Volume 5 , Issue 1 (November 2008) table of contents

Article No. 13

Year of Publication: 2008

ISSN:1549-6325

Authors

Dany Azriel	Ben-Gurion University of the Negev, Israel
Noam Solomon	Ben-Gurion University of the Negev, Israel
Shay Solomon	Ben-Gurion University of the Negev, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 146, Citation Count: 0

Additional Information:

abstract references index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1435375.1435388 What is a DOI?

ABSTRACT

The Tower of Hanoi problem is generalized by placing pegs on the vertices of a given directed graph G with two distinguished vertices, S and D, and allowing moves only along arcs of this graph. An optimal solution for such a graph G is an algorithm that completes the task of moving a tower of any given number of disks from S to D in a minimal number of disk moves.

In this article we present an algorithm which solves the problem for two infinite families of graphs, and prove its optimality. To the best of our knowledge, this is the first optimality proof for an infinite family of graphs.

Furthermore, we present a unified algorithm that solves the problem for a wider family of graphs and conjecture its optimality.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Allouche, J. P., Astoorian, D., Randall, J., and Shallit, J. O. 1994. Morphisms, squarefree strings, and the Tower of Hanoi puzzle. Amer. Math. Monthly 101, 651--658.
	2	D. Azriel , D. Berend, On a question of Leiss regarding the Hanoi Tower problem, Theoretical Computer Science, v.369 n.1-3, p.377-383, December, 2006
	3	Xiao Chen , Jian Shen, On the Frame--Stewart Conjecture about the Towers of Hanoi, SIAM Journal on Computing, v.33 n.3, p.584-589, 2004 [doi>10.1137/S0097539703431019]
	4	Dinitz, Y., and Solomon, S. 2006. Optimal algorithms for Tower of Hanoi problems with relaxed placement rules. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), T. Asano, Ed. Lecture Notes in Computer Science, vol. 4288, Springer, 36--47.
	5	Yefim Dinitz , Shay Solomon, Optimality of an algorithm solving the Bottleneck Tower of Hanoi problem, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-9, June 2008 [doi>10.1145/1367064.1367065]
	6	Dudeney, H. E. 1907. The Canterbury Puzzles (and Other Curious Problems). Thomas Nelson and Sons, London.
	7	Er, M. C. 1985. The complexity of the generalised cyclic Towers of Hanoi. J. Algor. 6, 351--358.
	8	Frame, J. S. 1941. Solution to advanced problem 3918. Amer. Math. Monthly 48, 216--217.
	9	Andreas M. Hinz, Pascal's triangle and the tower of Hanoi, American Mathematical Monthly, v.99 n.6, p.538-544, June-July 1992 [doi>10.2307/2324061]
	10	Korf, R. E., and Felner, A. 2007. Recent progress in heuristic search: A case study of the four-peg Towers of Hanoi problem. In Proceedings of the 20th International Joint Conferences on Artificial Intelligence (IJCAI), M. M. Veloso, Ed. International Joint Conferences on Artificial Intelligence, Menlo Park, CA, 2324--2329.
	11	Leiss, E. L. 1983. Solving the ‘Towers of Hanoi’ on graphs. J. Combin. Inf. Syst. Sci. 8, 81--89.
	12	Leiss, E. L. 1984. Finite Hanoi problems: How many discs can be handled? Congr. Numer. 44, 221--229.
	13	Lucas, E. 1893. Récréations Mathématiques. Vol. III. Gauthier-Villars, Paris.
	14	Lunnon, W. F. 1986. The Reve's puzzle. The Comput. J. 29, 478.
	15	Steven Minsker, The towers of Hanoi rainbow problem: coloring the rings, Journal of Algorithms, v.10 n.1, p.1-19, Mar. 1989 [doi>10.1016/0196-6774(89)90020-5]
	16	Poole, D. 1992. The Bottleneck Towers of Hanoi problem. J. Recreational Math. 24, 3, 203--207.
	17	Sapir, A. 2004. The Towers of Hanoi with forbidden moves. The Comput. J. 47, 20--24.
	18	Scorer, R. S., Grundy, P. M., and Smith, C. A. B. 1944. Some binary games. The Math. Gazette 280, 96--103.
	19	Stewart, B. M. 1939. Advanced problem 3918. Amer. Math. Monthly 46, 363.
	20	Stewart, B. M. 1941. Solution to advanced problem 3918. Amer. Math. Monthly 48, 217--219.
	21	Stockmeyer, P. K. 1994. Variations on the four-post Tower of Hanoi puzzle. Congr. Numer. 102, 3--12.
	22	Szegedy, M. 1999. In how many steps the k peg version of the Towers of Hanoi game can be solved? In Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS), C. Meinel and S. Tison, Eds. Lecture Notes in Computer Science, vol. 1563, Springer, 356--361.
	23	Wood, D. 1981. The Towers of Brahma and Hanoi revisited. J. Recreational Math. 14, 1, 17--24.