Tower of Hanoi, the Hard Way

Kai Birger Nielsen from Denmark has observed that the rules of the Tower of Hanoi puzzle may be bent a little still leaving it amenable to the recursive analysis. In his own words,

 

The rules of the game don't prohibit silly moves like moving the little ring from one peg to another and then back again, i.e. wasting two moves, but if you want to solve the game with as few moves as possible you don't want to waste moves.

A variation of the game is to solve the game using as many moves as possible without returning to a previous configuration of the rings.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

One way of doing this is:


Solve(N, Src, Aux, Dst)
    if N is 0 
      exit
    else
      Solve(N-1, Src, Aux, Dst)  // moves (N-1) small disks from Src to Dst
      Move from Src to Aux       // moves the largest disk from Src to Aux  
      Solve(N-1, Dst, Aux, Src)  // moves (N-1) small disks from Dst to Src
      Move from Aux to Dst       // moves the largest disk from Aux to Dst  
      Solve(N-1, Src, Aux, Dst)  // moves (N-1) small disks from Src to Dst

This uses 3n - 1 moves. You can describe any configuration of n rings on three pegs as an n-digit number with the digits 0, 1 and 2 and conversely you can convert any such n-digit number into a configuration of the n rings. Thus there are 3n different configurations and so you can at most use 3n - 1 different moves to move the pegs without repeating any configuration.

It is also possible to derive the recurrence relation

  TN = 3TN-1 + 2

similar to what has been done for the regular puzzle. T0 = 0 of course, implying TN = 3n - 1.

The states generated by the algorithm are all distinct. Were it not so, the algorithm would loop continuously. The easiest approach to proving that is by induction. Below, we list a sequence of moves generated by the algorithm for N = 3. The algorithm stops, there are no repetitions. Assume this is true for N = K, and verify that this assumption implies the assertion for N = K + 1. But the algorithm allows the largest disk (K + 1) on all three pegs. Between the movements of the largest, the smaller disks move by the algorithm until all of them moved from one of the pegs to another. By the inductive assumption, the movement of the K smaller disks does not create a repeated configuration. The transports of the smaller disks from a peg to another peg follow by a move of the largest disk to a new location so that the movements of the smaller disks due to the three different calls to the function Solve also can't create a repeated position.

So we have just proved that this is indeed the best way of wasting time.


For N = 3, the sequence of moves appears as

  1. Move from Src to Aux
  2. Move from Aux to Dst
  3. Move from Src to Aux
  4. Move from Dst to Aux
  5. Move from Aux to Src
  6. Move from Aux to Dst
  7. Move from Src to Aux
  8. Move from Aux to Dst
  9. Move from Src to Aux
  10. Move from Dst to Aux
  11. Move from Aux to Src
  12. Move from Dst to Aux
  13. Move from Src to Aux
  14. Move from Aux to Dst
  15. Move from Aux to Src
  16. Move from Dst to Aux
  17. Move from Aux to Src
  18. Move from Aux to Dst
  19. Move from Src to Aux
  20. Move from Aux to Dst
  21. Move from Src to Aux
  22. Move from Dst to Aux
  23. Move from Aux to Src
  24. Move from Aux to Dst
  25. Move from Src to Aux
  26. Move from Aux to Dst
  1. Tower of Hanoi
  2. Tower of Hanoi, the Hard Way
  3. Bicolor Towers of Hanoi
  4. 3-Colors Tower of Hanoi
  5. 3-Colors Tower of Hanoi (Algorithm)
  6. Hanoing
  7. Sierpinski Gasket and Tower of Hanoi

|Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny

71491622