COMP1927 - Tower of Hanoi


The object of the game is to move all the disks onto a different rod, whilst keeping each rod in descending order of height.

There's an intuitive iterative method; simply loop through, alternating between moving the smallest and next-smallest disk (right if even, and left if odd), to make the legal move, until it's sorted.

As well as a very elegant recursive way of doing this:


int hanoi (int numDisks, int from, int to, int using) {
   int numMoves = 0;
   if (numDisks == 1) { 
      printf ("Move a disk from pin %d to pin %d\n", from, to);
      numMoves = 1;
   } else {
      numMoves += hanoi (numDisks-1, from, using, to);  
      numMoves += hanoi (1, from, to, using);
      numMoves += hanoi (numDisks-1, using, to, from);
   return numMoves;



Hanoi is O(2n). Proof by induction.