The Explicit Formula of the Presumed Optimal Recurrence Relation for the Star Tower of Hanoi

Akihiro MATSUURA  Yoshiaki SHOJI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.492-498
Publication Date: 2019/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCP0013
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 
Tower of Hanoi,  four pegs,  star graph,  Frame-Stewart algorithm,  recurrence relation,  

Full Text: FreePDF(229.5KB)


Summary: 
In this paper, we show the explicit formula of the recurrence relation for the Tower of Hanoi on the star graph with four vertices, where the perfect tower of disks on a leaf vertex is transferred to the central vertex. This gives the solution to the problem posed at the 17th International Conference on Fibonacci Numbers and Their Applications[11]. Then, the recurrence relation are generalized to include the ones for the original 4-peg Tower of Hanoi and the Star Tower of Hanoi of transferring the tower from a leaf to another.