Friday, 16 December 2016

Exploring Tower of Hanoi - 2

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.





Suppose that our movement about the towers is restricted. We have three towers named A, B and C. Our n disks of different sizes are on tower A and we need to transfer disks to tower C via B. But we can only send disks from A to B, from B to C and from C to A. All other movement is restricted. What will be the minimum moves for this problem ?

In the original Tower of Hanoi problem, moving disk from any tower to any other tower will have the same number of minimum moves. But in this problem, moving disk from A to C and from A to B will have different number of minimum moves.

Let us assume that we need M( n ) moves for moving n disks from A to C.
Recursive steps to calculate M( n ) (moving disk from A to C) are : 
Step 1 : Move (n - 1) disks from tower from A to C recursively. Moves required are M(n - 1).
Step 2 : Move nth disk from A to B. Only one move is required.
Step 3 : Move all of (n - 1) from C to A recursively. Lets assume that moves required are N(n - 1).
Step 4 : Move nth disk from B to C. Only one move is required.
Step 5 : Move all of (n - 1) disks from A to C recursively. Moves required are M(n - 1).
Step 6 : ???
Step 7 : Profit. (Task complete !!!)
Total moves required, M( n ) = 2 * M(n - 1) + N(n - 1) + 2

Now we need to calculate N(n - 1). But before that, what is the difference between N( n ) and M( n ). M( n ) is the number of moves to move n disks from A to C. N( n ) is the number of moves to move n disks from A to B.
Recursive steps to calculate N( n ) (moving disk from A to B) are : 
Step 1 : Move (n - 1) disks from tower from A to C recursively. Moves required are M(n - 1).
Step 2 : Move nth disk from A to B. Only one move is required.
Step 3 : Move all of (n - 1) from C to B recursively. Moves required are M(n - 1).
Step 4 : ???
Step 5 : Profit. (Task complete !!!)
Moves required, N( n ) = 2 * M(n - 1) + 1

Therefore, total moves required to move n disk from A to C, M( n ) = 2 * M(n - 1) + 2 * M(n - 2) + 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. Here is the code in C to implement this : Github Gist

No comments:

Post a Comment