Tower of Hanoi: Grey Code

When using Grey Code to determine the minimum number of moves in the Tower if Hanoi, it is easy to see that you can only use each subset once.

So for 4 disks 3 pegs the gery code would be;

Start {0 0 0 0};

Move the first disk {0 0 0 1}

Move the second disk{0 0 1 1};

Move the first disk onto the second disk  {0 0 1 0};

Move the third disk to the empty peg now{0 1 1 0};

Move the first disk onto the forth disk  {0 1 1 1};

Move the second disk onto the third disk  {0 1 0 1};

Move the first disk on top of the second disk{0 1 0 0}:

Now move the forth disk{1 1 0 0};

Move the first disk onto the forth disk{1 1 0 1};

Move the second disk to the empty peg{1 1 1 1} ;

Move the first disk onto the second disk  {1 1 1 0};

Move the third disk   onto the forth disk  {1 0 1 0};

Now move the first onto the empty peg{1 0 1 1};

 Move the second onto the third{1 0 0 1};

 And  finaly move the first onto the second disk{1 0 0 0}

As you can easily see in order for this to be the minimum number of moves you have to only use each subset once.

~ by mathwizhoax on December 11, 2008.