The past couple of weeks we’ve been looking at Gray Codes and how they help with the Tower of Hanoi game. After painstaking brainstorms, Professor Davis realized that the Gray Codes indicate when a disk is moved, and not where it is moved to. With this epiphany, it made Gray Codes significantly easier to read and decipher. Using Gray Codes, we can find patterns the game “creates” with any amount of disks for the game.
The downside to Gray Codes is without a visual, you can’t really write up the code frame. It’s easiest to use when you can see where you are moving each disk. Last week, we discussed the ToH game with 4 and 5 pegs. Playing the game through the first couple of disks we reached the following:
n disks…. # of moves
….2………….3
….3………… 5
….4………… 9
From here, a pattern seemingly appeared with the number of moves. The moves followed 2, 2, 4, and the “logical” thought was the next move will be 17, since it doubled from 3 disks to 4. With some manual work, I found that 5 disks gives you 13 moves, and 6 disks gives you 17. This shot down the pattern idea.
One thing I did notice is each disk will be moved once, twice, or four times for three disks or more. The odd this is it doesn’t stay constant. For example (with disks being 1 to n, 1 being the largest), the pattern for 4 disks is 1, 2, 2, 4 (starting with disk 1 through disk 4 respectively). With 5 disks, the pattern is 1, 2, 4, 2, 4, and with 6 disks it’s 1, 2, 4, 2, 4, 4.
Filed under: Uncategorized
