Definition:
The Tower of Hanoi problem is a puzzle which can be solved by mathematically and can be implemented in programming code as well. The tower is also called Tower of Brahma or Lucas’ Tower. In this, game there are three pegs and one one of them hold n disks. n disks are ordered from higher radius to lower radius from the bottom to top.
Objective:
The objective is to move all the disks to to another peg , Calculate minimum number of moves needed & stats of three pegs after specific number of moves. But following conditions have to be fulfilled.
- Single disk can be moved at a time. No concurrency.
- Upper disk has to be moved from one peg to another.
- A disk of higher radius can not be placed on a disk of lower radius.
Following image explains the conditions-
The gif is collected from tutorialspoint.com
Minimum Moves Needed to Finish the Game (Recursive Solutions)
Thinking Approach
For ease of remembering, lets think disks are numbered 1 to n from top to bottom. Now we will explore the puzzle in reverse way. We think first to move n‘th disk from first peg to third peg. But before that we need to move n-1 disks to second peg. Upon completion of moving n-1 disks to second we we will move n‘th disk from first peg to third peg and then move n-1 disks from second peg to third peg.
So, to finish shifting all disks, move orders become -
move n disks from first peg to third pegs = Move (n-1) disks from first peg to second peg + move n’th disk from first peg to third peg + Move (n-1) disks from second pegs to third peg.
Equation,
T(n) = T(n-1)+1+T(n-1)
Now to move n-1 disks from first peg to second pegs, initially we need to move n-2 disks from first pegs to third pegs then bring n-1‘th disk from first peg to second peg. Then again move n-2 disks from first pegs from third peg to second pegs. So, move orders become -
move n-1 disks from first peg to second peg = move n-2 disks from first peg to third peg + move n-1’th disk from first peg to second peg + move n-2 disks from third peg to second peg.
Equation,
T(n-1) = T(n-2)+1+T(n-2)
Now will find the solution for T(n-2), T(n-3), T(n-4) ……. T(0). T(0) = 0, as we know that one disk require one move. So, rest equations will be-
T(n-2) = T(n-3)+1+T(n-3)
T(n-3) = T(n-4)+1+T(n-4)
……………………………………..
……………………………………..
……………………………………..
T(1) = T(0)+1+T(0)
T(0)=0
Lets think there are 4 disks. Now I will show a tree to solve the problem for T(4);
T(4) | T(3)+1+T(3) / \ T(2)+1+T(2) T(2)+1+T(2) / \ / \ T(1)+1+T(1) T(1)+1+T(1) T(1)+1+T(1) T(1)+1+T(1)
From above tree we see that the solution of T(n) depends on T(n-1) and T(n-1) depends on T(n-2) and so on until base case T(0)=0 comes. If we know solution of 0 disk we can find the solution of any number of disks as long as there are three pegs only.
Pseudocode for Programming ( O(2^n) Time Complexity)
1 | def TotalMoves(N): |
We can optimize above pseudocode for better time complexity. We do not need to call TotalMoves(N-1) twice. Rather we can just write 2*TotalMoves(N-1) there. Pseudocode will become -1
2
3def TotalMoves(N):
if N == 0: return 0
return 2\*TotalMoves(N-1)+1
The time complexity of above code is O(2^n). We can bring it to linear time by doing some math. See below for linear solution.
Mathematical Solution ( O(1) Time Complexity )
From above discussions of recursive solution of The Tower of Hanoi, we can write the recurrence relation. The relation is -
T(n)=2*T(n-1)+1
we know, T[0] = 0
Let, U[n] = T[n]+1
So, U[0] = T[0]+1
=> = 1
Now, U[n] = T[n]+1
=> = (2*T[n-1]+1)+1 ; From equation, we know T[n] = 2*T[n-1]+1
=> = 2*T[n-1]+2
=> = 2*(T[n-1]+1)
=> = 2*U[n-1]
=> = 2*2*U[n-2]
=> = 2*2*2*U[n-3]
...................
...................
...................
=> = 2*2*2*...2*1
=> U[n] = 2^n ; At finishing stage total number of 2 will be n.
=> T[n]+1 = 2^n
=> T[n] = 2^n-1
T[n] = 2^n-1 is the equation to count minimum moves need to finish the Tower of Hanoi game. Note, if we know the mathematical equation of The tower of Hanoi problem then we can find the solution in linear time.
WhatsUP