tomclegg.net |
Towers of Hanoi Posted March 25, 2001 Mostly Mozart is sponsored by Comfort and Joy, a unique children's store. The other day, I was trying to fall asleep, and since I resolved a long time ago never to count sheep in order to fall asleep, I started listing programming languages instead. One for each letter of the alphabet. But don't get scared. This is not going to be a show about programming. This is just the setup. A and B are pretty easy. Everyone knows about assembly language and BASIC. C is even easier, since there's a language called C. D is for Dylan; E is for Expect. F is obviously for Fortran, or perhaps Forth. G is for ghostscript, a non-proprietary language that happens to be compatible with Postscript (tm). Then I got stuck on H. It could stand for HTML, but it's not a sufficiently powerful language. For example, it doesn't have anything resembling loops. It might be the most famous computer language, but it doesn't have loops, so it doesn't qualify. Then I thought that there should be a programming language called Hanoi. I don't know if there is, but there should be. I expect that everyone who's ever created a programming language knows how to play the Towers of Hanoi game. It's a great demonstration of things like recursion and algorithm analysis. And it's been around for thousands of years. Here's how it works. You've got a small board, with three pegs pointing straight up. The first peg has eight different-sized rings on it, with the smallest ring at the top and the biggest ring at the bottom. The other two pegs are empty. Your task is to move all of the rings from the first peg onto the second peg. Which sounds easy, of course, until you hear the rules. The first rule is that you can only pick up one ring at a time, and you have to put it onto another peg immediately. The second rule is that you can't put a bigger ring on top of a smaller ring. And that's all the rules. You don't need pegs and rings in order to play the Towers of Hanoi. If you don't have pegs and rings, you can just cut out eight pieces of paper of different sizes, or use different sizes of coins, or whatever. But if you do use pegs and rings, then at least everyone will know what you're doing. You don't want to be caught in your room on a sunday afternoon, staring at little piles of coins, carefully moving them back and forth without breaking the rules. People will think you're crazy. While you listen to the music, have a little game of Towers of Hanoi. If you're planning to move one ring every 8 seconds, you'll need just 8 rings to take you to the end of this Mozart piece. If you're going to move one ring every second, then 11 rings will take you through the next half hour. And if you want to play at that rate 20 hours a day until next week's show, then you'll need about 19 rings. But I don't recommend that. It's probably bad for your brain. Before the music starts, here are the rules again: You need 8 rings of different sizes, and three real or imaginary pegs to put them on. You start out with all 8 rings on the first peg, the biggest one at the bottom and the smallest one at the top. The object is to move all the rings onto one of the two empty pegs. And there are only two rules. You can only move one ring at a time; and you can't put a bigger ring on top of a smaller ring. Have fun, and play nice! --- Comfort and Joy is happy to sponsor Mostly Mozart. My name is Tom Clegg, and today I'm teaching you to play a solitaire game called the Towers of Hanoi. If you caught the first few minutes of the show, you've had a little fun with the Towers already. And perhaps you were paying really close attention to the bit about how long it takes to play a game with 19 rings. 20 hours a day for 7 days, moving one ring per second. That's 504,000 seconds. Which is almost enough to make 524,287 moves. And in case you didn't know this already, it's not a coincidence that 524,287 equals 2 to the power of 19, minus 1. Let's go over the rules again. You start with 8 rings, smallest one at the top. You can move one ring at a time, and you can't put a bigger ring on top of a smaller ring. So the first two moves were probably pretty obvious. You take ring #1, the smallest ring, and put it on an empty peg. Then you take ring #2, and since you can't put it on top of ring #1, you have to put it on the other empty peg. Now what do you do? You can't do anything with ring 3, because you can't put it on top of ring 1 or ring 2, and there are no more empty pegs. So, first you move ring 1 onto ring 2, and you're left with an empty peg where ring 1 used to be. Now, before you take ring 3 off the first peg and put it on the empty peg, you should notice something. You just made 3 moves. And you just finished a 2-ring game of Towers of Hanoi. You took two rings, smallest one at the top, and moved them on to another peg, without breaking either of the rules. Now you can move ring 3 onto an empty peg. That's your fourth move. Then you move rings 1 and 2 onto ring 3, using the same sequence of three moves that you just used to get them off the first peg in the first place. That's a total of 7 moves. So. Moving 1 ring takes 1 step. Moving 2 rings takes 3 steps. Moving 3 pegs takes 7 steps. I think there's a pattern emerging. In order to move three rings, you first move the 2 top rings onto one empty peg, then you move ring 3 onto another empty peg, then you move the 2 top rings on top of it. So, to play a 3-ring game, you simply play a 2-ring game, take one step to move ring 3, then play another 2-ring game. So the number of steps it takes to play a 3-ring game is twice what it takes to play a 2-ring game, plus one. Twice 3, plus 1, equals 7. So, if it takes 7 steps to play 3 rings, how many steps does it take to play 4 rings? Twice 7 is 14, plus 1 is 15. 5 rings? twice 15 is 30, plus 1 is 31. Now if you know any of the powers of 2, you'll notice something about this sequence of numbers. 1, 3, 7, 15, 31. If not, you'll certainly notice something about them if I add 1 to each of them. 2, 4, 8, 16, 32. Each time you add another ring to the game, it takes you twice as many steps to finish. This means that the time it takes to play Towers of Hanoi grows exponentially with the number of rings. If you stack up a few hundred rings, the number of steps required to finish the game will be pretty close to the number of particles in the universe. |