Tuesday, 20 December 2016

Exploring Tower of Hanoi - 3

Intro from my last blog : This is more of an article than a blog but it is my exploration. On solving for different n's , I found that the bottom disk always moves only once. Similarly, second disk from the bottom moves 2 times. Third from the bottom always moves 4 times. And so on, they form the series => 1, 2, 4, 8, ... , 2^(n - 1) . The sum of these is of course equal to 2^n - 1 which was already mentioned above.

It been a while since we have been looking at the old Tower of Hanoi problem with same constraints. What if we have more than 3 towers ? This time we are exploring the Tower of Hanoi when the number of disks, n > 0 and number of towers, p > 2. 

Many of the mathematicians have tried at this problem and if we google their research we will get to some non - trivial and rigorous mathematics. Just google it, and find them yourself.

I don't want to go into mathematics because firstly I don't get it and secondly it is not proven yet that fits all possible combinations of n and p to find the minimum moves. I have written a C code which use dynamic programming to find and print minimum moves for any given n and p such that n > 0 and p > 2. What it does is, it splits the very first pile of disks at some k which is varying from 1 to n. After each split, the problem is divided into two sub problem of k disks and n - k disks.

What happens next will blow your mind !!! This k disks and p - 1 towers problem is solved first and recorded in a 2 - D matrix of moves which stores moves for x disks and y towers. Then n - k disks and p towers problem is solved afterwards. Both of them are only stored in the matrix if they are smaller then the previous problem. This is why, initially matrix was filled with infinity.

The result for k disks and p - 1 towers and n - k disks and p towers is added and also stored in the same matrix if it less then the previously stored value. This will be enough for finding the minimum number of moves for n disks and p towers.

To print the actual moves along with the number of moves, we will need another matrix which will store the best split for x disks and y towers. Number of moves will be printed in the same way as the the number of moves were calculated.

Both of the matrix will be filled at the same time and the printing of the moves will be done separately after both of the matrix are filled. Whole of this can be done with only the best split array but then the time complexity will be higher. It is an example of time-memory compensation. This size of the array needed will be n x (p - 3).

I know that nobody would like to read somebody else's code but for the completeness of this blog I think that I should give the code as well. Though this problem may look easy to some of you but it was a great challenge for me. I wrote this code just after I learnt dynamic programming. At that time, I knew very less things related to programming. Here I present the C implementation for this problem : Github Gist

No comments:

Post a Comment