# 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