Towers of Hanoi

The Towers of Hanoi refer to an old puzzle with three pegs and a pile of disks. The disks are stacked in order with the biggest on the bottom and the smallest on the top, all together on one peg. The idea is to move all the disks from that peg to another with the following restrictions :

1. You can only move one disk at a time.
   
2. You can't put a big disk on a smaller one.

Two of my computing courses so far have said that this is a perfect example for a recursive function. One of them even said that you could only solve it using recursion. When the textbook said so as well, I started thinking. It goes something like this :

If there are 3 disks on peg 1 which we want to get to peg 3, we get the following moves :

Move :	1	2	3	4	5	6	7
Move piece :	1	2	1	3	1	2	1
From peg :	1	1	3	1	2	2	1
To peg :	3	2	2	3	1	3	3

If you look just at which pieces are moved, you see a simple pattern. Piece 1 is moved every second move. Piece 2 is moved every second move left over, etc. This suggests a relationship with binary and indeed, the piece number is 1 more than the number of zeros at the end of the binary representation of the move number.

e.g. move 3 is 11 base 2 which has 0 zeros so you get piece 1
e.g. move 4 is 100 base 2 which has 2 zeros so you get piece 3
etc.

This can be represented using the following bit of C code :

for(int peicenum = 1;movenum & 1;movenum >>= 1, peicenum++)
  ;

A little bit more inspection about the movement of the pieces brings up another useful bit of information. If the pegs are arranged as follows :

  1

2   3

All this can be combined into a "simple" function :

void FindMove(int movenum)
{
  for(int peicenum = 1;movenum & 1;movenum >>= 1, peicenum++) // Find piecenum
    ;

  movenum >>= 1; // Find move number for this particular piece

  frompeg = 1 + (movenum % 3); // Calculate pegs for anti-clockwise
  topeg = 1 + (frompeg % 3)

  if(piecenum & 1)  // Is odd numbered piece
  {
    frompeg = (4 - frompeg) % 3; // Reverse direction  1->1, 2->3, 3->2
    topeg = (4 - topeg) % 3;
  }

  DoMove(frompeg, topeg);
}

Notes :

1. Notice that the function doesn't need to know the total number of disks.
2. The destination peg is not given either. It is wherever the biggest disk goes to. If this is the wrong peg, renumber the pegs.
3. I'm not claiming that this is the most efficient way of doing it. Using lookup tables it is possible to remove the last three uses the the % (mod) operator, since these operations only map {1,2,3} onto {1,2,3}. The first use could be removed if you had a table to keep track of where the disk are.