Legend has it that long ago, a group of monks in the Far East were charged with the task of moving 64 golden discs from one pole to a third. Once this task was completed, the world would come to an end. However, the monks must follow a set of rules: no larger disc may be placed on top of a smaller disc. With those rules in mind, even if the monks move one disc per second, it will still take them 18446744073709551615 seconds to complete their task, which comes out to around 600 billion years.

Although the Towers Of Hanoi problem is usually used as an introduction to recursion, it's actually much better implemented iteratively:

#include<stdio.h>

void main()
{
  int i, x, max;
  printf("Number of discs?");
  scanf(" %d",&i);
  int max = 1 << i;
  for (x = 1; x < max; x++)
    { printf("Move a disc from %d to %d\n", (x & x-1) % 3, ((x | x-1) + 1) % 3); }
}
Quickest solution for three discs:

1 to 3; 1 to 2; 3 to 2; 1 to 3; 2 to 1; 2 to 3; 1 to 3

You can approach this puzzle in a slightly different manner.

If you label the disks instead of the pegs, and then list the disk that's moved with each step, the binary nature of the solution becomes apparent.

Let's label the smallest disk 1, the next larger disk 2, and so on.
Moving a tower of N disks then proceeds recursively:
  1. Move disks 1 through N-1 out of the way, as if there were no other disks.
  2. Move disk N.
  3. Move disks 1 through N-1 back on top of disk N.
To move one disk, you obviously move disk 1. To move two disks, move disk 1, move disk 2, then put disk 1 on top of it.

The string of disks to be moved with each step is then

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 ....

Also notice that the number of the disk you move is the least order bit1 of the binary number representing the step number.

To solve an actual "Tower of Hanoi" problem, keep two rules in mind:
  • The tower can only be moved if you never put an odd-numbered disk on top of another odd-numbered disk without an even-numbered disk in between. Also, never put an even-numbered disk on an even numbered disk.
  • In order to move an odd number of disks to a particular peg, start by moving the first disk to that peg. For an even number of disks, move the first disk to the other peg.
Following the above rules plus the disk-numbering string leads to a unique solution of exactly 2N-1 steps for N disks.

If the monks are able to move a disk once a second, it will take 584,542,046,090 years, 228 days, 15 hours, 14 minutes, and 45 seconds to move the entire tower of 64 disks!
1Or the least-order bit, minus one, depending on how you number the bits.

It is possible to generate a simple fractal that provides a solution to Towers of Hanoi.

If the three towers are arranged in a circle, we can impose the restriction that pieces should always be moved to the next available tower in a clockwise direction, respecting the constraint that a piece may not be put on top of a smaller one.

The construction of the fractal is as follows:

The basic construct is the shape:

     |
 a---+---c
     |
     |
 b---+---d
     |

This is the first generation. To create the second generation, reproduce the construct between points a and b, as well as points c and d:

            |
            |
     +------+------+
     |      |      |
  ---+---   |   ---+---
     |      |      |
     |      |      |
  ---+---   |   ---+---
     |      |      |
     +------+------+
            |
            |

For the basic 3-ring version of Hanoi, a 3rd-generation fractal is required.

                |
       +--------+--------+
       |        |        |
   +---+---+    |    +---+---+
   |   |   |    |    |   |   |
 --+-- | --+--  |  --+-- | --+--
A  |   |   |    |    |   |   |  B
 --+-- | --+--  |  --+-- | --+--
   |   |   |    |    |   |   |
   +---+---+    |    +---+---+
       |        |        |
       +--------+--------+
                | 

The solution can be found by tracing a straight path from A to B. Whenever the path crosses once of the constructs, a note is made of which generation it is from:

                |
       +--------+--------+
       |        |        |
   +---+---+    |    +---+---+
   |   |   |    |    |   |   |
 --+-- | --+--  |  --+-- | --+--
A~~3~~~2~~~3~~~~1~~~~3~~~2~~~3~~B
 --+-- | --+--  |  --+-- | --+--
   |   |   |    |    |   |   |
   +---+---+    |    +---+---+
       |        |        |
       +--------+--------+
                |

This sequence gives the order in which the rings should be moved to complete the puzzle, bearing in mind the restriction of movement described above. Each generation number represents a ring size; 1 being the largest ring, down to 3 being the smallest ring.

In general, N-rings require N generations to provide the solution.

Log in or register to write something here or to contact authors.