- Activity involving three baby-ring stacking toys:
- Provide each group of students with three baby ring-stacking toys, but with only one set of rings (4 rings is enough).
- Explain the requirements of Tower of Hanoi
- Goal: Move the rings from one post to another.
- Restrictions:
- You can only move one ring at a time.
- You can’t put a bigger ring on top of a smaller ring.
- Have students document their process as they go so that they can reproduce their solution and explain it to the class.
- Start by giving the students 5-10 minutes to try and work through the solution.
- If students get stuck walk them through the case of needing to move only 1 ring.
- If no solution is found, start by removing the top three disks from the first post and placing them on the second post. Then ask the class how they would start solving for only needing to move the bottom disk from post 1 to post 3 (base case).
- Write the steps to moving the disk:
- which direction it moved,
- how far it moved,
- and the instructions for placing it on the last post.
- Then move the three rings from post 2 to post 3.
- So students see that the easiest solution is to move 3 rings to different cones, after the initial ring is moved.
- Now, put all the rings back and start again.
- Write the steps to moving the disk:
- Scaffold according to the following script:
- "We would want to find a way to move 3 rings, and get them to the middle cone. So if we start by moving ring 1 to cone 2, then ring 2 to cone 3, ring 1 to cone 3, ring 3 to cone 2, ring 1 back to cone 1, ring 2 back to cone 2, then ring 1 back to cone 2 (now all the rings except the largest one are on cone 2, so move ring 4 to cone 3, then move ring 1 to cone 3, ring 2 to cone 1, ring 1 to cone 1, then move ring 3 to cone 3 (two largest rings are on the 3rd post), then move the smallest (ring 1) to post 2, and ring 2 (now alone on post 1) and be moved to post 3, then it’s just a simple matter of moving ring 1 to post 3 and they are all in order!"
- After students create the algorithm, you can show them this completed solution video
- Here is a walk through of this activity from Carnegie Mellon University that talks through recursion in the solution algorithm.
- Possible Extension using Alice:
- Below is a storyboard and sample code for the Towers method, which will animate the solution to the Towers of Hanoi puzzle.
- Storyboard:
- Code:
- Storyboard:
- Check out Chapter 9 section 2 (p. 361) of William Taffe’s book called Programming in Alice.
- You can provide this section to students to give them an in depth explanation of how to write and solve the Towers of Hanoi puzzle in Alice.
- Below is a storyboard and sample code for the Towers method, which will animate the solution to the Towers of Hanoi puzzle.