An Optimal Algorithm for Solving the Towers of Hanoi Problem with the Least Storage Used

Yu-Kumg CHEN  Chen-An FANG  Fan-Chieh CHENG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.2   pp.240-242
Publication Date: 2011/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.240
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
Towers of Hanoi,  data structure,  algorithm,  mathematic,  game,  

Full Text: PDF(784.1KB)>>
Buy this Article




Summary: 
The Towers of Hanoi problem is a classical problem in puzzles, games, mathematics, data structures, and algorithms. In this letter, a least memory used algorithm is proposed by combining the source array and target array for comparing the sizes of disk and labeling the disks in the towers of Hanoi problem. As a result, the proposed algorithm reduces the space needed from 2n+2 to n+5, where n represents the disks number.