Showing posts with label hanoi. Show all posts
Showing posts with label hanoi. Show all posts

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
 
Stats