For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Explicit Formula of the Presumed Optimal Recurrence Relation for the Star Tower of Hanoi
Akihiro MATSUURA Yoshiaki SHOJI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Tower of Hanoi, four pegs, star graph, Frame-Stewart algorithm, recurrence relation,
Full Text: FreePDF(229.5KB)
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. 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.