An algorithm for tower of hanoi with four or more poles

An algorithm for tower of hanoi with four or more poles

Creators Takanami Itsuo

Creators Inoue Katsushi

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.

[ISSN]0386-3433

[NCID]AA0086073X