# 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.
One way of doing this is:
This uses 3 It is also possible to derive the recurrence relation
similar to what has been done for the regular puzzle. 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 So we have just proved that this is indeed the best way of wasting time. |

For N = 3, the sequence of moves appears as

- Move from Src to Aux
- Move from Aux to Dst
- Move from Src to Aux
- Move from Dst to Aux
- Move from Aux to Src
- Move from Aux to Dst
- Move from Src to Aux
- Move from Aux to Dst
- Move from Src to Aux
- Move from Dst to Aux
- Move from Aux to Src
- Move from Dst to Aux
- Move from Src to Aux
- Move from Aux to Dst
- Move from Aux to Src
- Move from Dst to Aux
- Move from Aux to Src
- Move from Aux to Dst
- Move from Src to Aux
- Move from Aux to Dst
- Move from Src to Aux
- Move from Dst to Aux
- Move from Aux to Src
- Move from Aux to Dst
- Move from Src to Aux
- Move from Aux to Dst

- Tower of Hanoi
- Tower of Hanoi, the Hard Way
- Bicolor Towers of Hanoi
- 3-Colors Tower of Hanoi
- 3-Colors Tower of Hanoi (Algorithm)
- Hanoing
- Sierpinski Gasket and Tower of Hanoi

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

Copyright © 1996-2018 Alexander Bogomolny68931195