Tower of Hanoi with a restriction of no direct transfers

We need to solve the Tower of Hanoi problem, with this additional restriction : direct moves between the origin and destination towers is disallowed. All other restrictions still apply  as-is.

For example, if a single disk is to be moved from Tower A to Tower B (using Tower C), then moving the disk directly from A to B is not allowed. The disk must be first transferred to Tower C and then to Tower B.

The purpose is to find the shortest sequence / number of moves we can do this in : 
  • T(0) = 0 (basis case, nothing to move)
  • T(1) = 2 (from above)
  • T(n-discs) = ???
Source : Concrete Mathematics (2nd Edition) Ex. 1.2

2 comments:

Madhur Kumar Tanwani said...

If we work out the small cases, we see that :

T(1) = 2
T(2) = 8
T(3) = 26

Also, to transfer the 'n'th disc from Tower A to Tower B, we must first transfer the previous 'n-1' discs from Tower A to Tower B. Now, since direct transfers are forbidden, the approach will be this :
1.> move the 'n-1' discs from Tower A to Tower B
2.> move 'n'th disc to Tower C
3.> move 'n-1' discs from Tower B to Tower A
4.> move 'n'th disc from Tower C to Tower B
5.> Now recursively transfer the 'n-1'th disc from Tower A to Tower B

From above we can see that

T(n) = T(n-1) + 1 + T(n-1) + 1 + T(n-1)

which means
T(n) = 3 * T(n-1) + 2
solving this :
T(n) + 1 = 3 * [T(n-1) + 1)
using U(n) = T(n) + 1, we get
U(n) = 3*U(n-1)
which can be solved to be :
U(n) = 3^n (for n > 0)

Hence,
T(0) = 0 and
T(n) = 3^n - 1 (for n > 0)

Anonymous said...

Hi

Do you have any pseudocode for this?

 
Stats