Solving Tower Of Hanoi Puzzles: Minimum Moves Solutions

[artmaker]

When reading a Martin Gardner book, I came across a method of binary counting using "Reflective Binary Gray Codes". This involves counting in binary such that One and ONLY ONE bit changes as the counting proceeds. This method of counting has many applications that he discussed, but the one that was quite interesting was the minimum-move solutions to Tower Of Hanoi Puzzles with various number of rings.

Reflective Binary Gray Code Counting is done as follows:

1. Write the bits in binary.
2. Starting with the rightmost bit (Bit Number One)
3. If and ONLY IF the bit immediately to the left (Bit Number Two) is a "1", change Bit Number One.
4. Move to Bit Number Two
5. If and ONLY IF the bit immediately to the left (Bit Number Three) is a "1", change Bit Number Two.
6. Keep going towards the leftmost bit until done.(to the left of the leftmost bit is an assumed "0")

Example:

Binary 5 is "101"; It's Reflective Binary Gray Code is "111"
Binary 12 is "1100"; It's Reflective Binary Gray Code is "1010"

The minimum-moves solution to Tower Of Hanoi Puzzles is equal to: (2 ^ Rings) -1
If you generate a Reflective Binary Gray Code from 1 to this minimum-moves solution, the only bit that changes as you count represents the Ring to move.

I wrote a program to solve up to an 8-Ring Puzzle (255 Moves). Attached are the screen shots for a 4-Ring Puzzle.

Screen Number One

Screen1.gif (31.83 KiB) Viewed 3220 times

[artmaker]

Go to this url to play the game online (from one through eight rings)

http://www.dynamicdrive.com/dynamicinde ... rhanoi.htm

What's really good is that at the bottom of the page there is a link to "Dynamic Drive", which opens a window where your can download the exact htm that you are playing online, and you can modify the 'delay' in the source code so that you can study the moves. The online page has an auto-solution-delay of 200 ms, and the auto-solve moves are way too fast to study. With the copy I downloaded, I changed ths to 2500 ms, which is where I can better study the moves (seems as if even-ring puzzles "work" the final peg and odd-ring puzzles "work" the center peg.

It is one part of the puzzle about WHICH ring to move; however, the rest of the puzzle is to understand WHERE to move it.