Tower of Hanoi, the Hard Way

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:

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 3ⁿ - 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 3ⁿ different configurations and so you can at most use 3ⁿ - 1 different moves to move the pegs without repeating any configuration.

It is also possible to derive the recurrence relation

similar to what has been done for the regular puzzle. T₀ = 0 of course, implying T_N = 3ⁿ - 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.