Generalized Towers of Hanoi  Optimal Algorithm 
Written by Mike James  
Saturday, 17 December 2011  
The Towers of Hanoi problem is well known and solved, but there are generalizations of it that still present some problems. Now we have an optimal algorithm for the 4peg problem  can this be generalized to the npeg problem? The Towers of Hanoi puzzle was introduced in 1833 and consists of three pegs and a stack of disks of different sizes. The objective is to transfer all of the disks from the start peg to the final peg by moving one disk at a time to another peg, subject to the constraint that you never put a bigger disk on a smaller disk.
There are a number of algorithms that solve the problem with the smallest number of moves and they are all equivalent, be they iterative or recursive. You can prove that the ndisk 3peg problem can be solved in 2^{n}1 moves. In 1909 a puzzle book included a 4peg version of the game with the name "The Reve's Puzzle". This is of course the first in a sequence of n,m puzzles with n disks and m pegs  the standard puzzle being n,3 and the Reve's Puzzle being n,4. Clearly any generalized puzzle has a solution because you can simply ignore the additional pegs and treat it as an n,3 problem which has a wellknown algorithm. However, the algorithm is only provably optimal for the n,3 problem and not the n,4 or n,m problem. That is, you can solve the n,m problem in 2^{n}1 but can it be done fewer steps and what is the minimum number of steps required? Given you have some additional pegs it seems very reasonable to suppose that these can be used to reduce the number of moves but what is the optimal algorithm? In 1941 the American Mathematical Monthly published two equivalent algorithms. by Frame and Stewart, that solved the general n,m problem, but neither was proved optimal  they just did the job faster than the standard Towers of Hanoi algorithm. The Stewart/Frame algorithm is for n disks, m pegs and T( n,m) is the minimum number of moves for an n,m problem:
The entire process takes 2T(k,m) + T(n − k,m − 1) moves. Therefore, the count k should be picked for which this quantity is minimum. The whole problem can be solved recursively, but only if no algorithm can be found which does the job with fewer moves. Now Bijoy Rahman Arif of IBAIS University claims to have proved that Frame's algorithm is optimal, but only in the case when m = 4. In other words, we now have a solution for the 4peg Towers of Hanoi problem that is provably optimal and will move the disks in T(n,4) = min over k of { 2T(k,4) + T(n − k,3) } Can this result be generalized to T(n,m) for m>4? Read the paper to find out more. More InformationOn the Footsteps to Generalized Tower of Hanoi Strategy arXiv:1112.0631v1 Update Another proof:To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.


Last Updated ( Saturday, 17 March 2012 ) 