Technology reports of the Yamaguchi University

Back to Top

Technology reports of the Yamaguchi University Volume 2 Issue 2
published_at 1978-12

An algorithm for tower of hanoi with four or more poles

An algorithm for tower of hanoi with four or more poles
Takanami Itsuo
Inoue Katsushi
fulltext
305 KB
KJ00004350984.pdf
Descriptions
For the case of four or more poles, we propose a recursive procedure not using the dynamic programmming technique. Then in a certain proposed algorithm we derive an explicit expression for the number of moves of disks as a function of N disks and m poles. In this algorithm the number of moves decreases monotoneously in terms of m but its limiting value is 3^<「log_2N」> although 2N+1 is the minimum number of moves for m≧N+1. So we give a modified algorithm and its associated recurrence equation for the number of moves. This equation is solved numerically since it is difficult to derive the explicit expression for its solution. This result shows that the modified algorithm is near optimal.