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 4-peg problem - can this be generalized to the n-peg 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 n-disk 3-peg problem can be solved in 2ⁿ-1 moves.

In 1909 a puzzle book included a 4-peg 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 well-known 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ⁿ-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:

1. For some k,  1<=k<m, transfer the top k disks to a single peg other than the start or destination pegs, taking T(k,m) moves.
2. Without disturbing the peg that now contains the top k disks, transfer the remaining n − k disks to the destination peg, using only the remaining n  − 1 pegs, taking T(n − k,m − 1) moves.
3. Finally, transfer the top k disks to the destination peg, taking T(k,m) moves.

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 4-peg 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 Information

On the Footsteps to Generalized Tower of Hanoi Strategy arXiv:1112.0631v1

Update Another proof:

What is the least number of moves needed to solve the 4-peg Towers of Hanoi problem? Roberto Demontis arXiv:1203.3280v1

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.