PD4CS

Towers of Hanoi is a puzzle invented by the French mathematician Edouard Lucas in 1883.  Quite likely, students have played or seen a version of Towers of Hanoi as  it shows up in game stores and other venues.

The game consists of three pegs and a number of disks of different sizes arranged in decreasing order on Peg A.  The object of the game is to move the entire stack of disks from peg A to peg C while obeying the following rules: Only one disk can be moved at a time No disk may be placed on top of a smaller disk.

Students should be able to solve the puzzle, especially when there are not too many disks, by simply trying things out. However, a systematic approach that can be used for any number of disks is not immediately obvious until a recursive approach is discovered. The recursion operates as follows (we use 5 disks as shown above):

1. To move a tower of 5 disks from A to B, first move a tower of 4 disks from A to B
2. Move the bottom peg (the largest one) from A to C
3. Move the tower of 4 disks from B to C.

Of course, moving a tower of 4 disks from A to B involves moving a tower of 3 disks from A to C.  This pattern continues until the final tower contains only 1 disk (the base case) in which case it involves simply moving one disk to the desired peg.

Give students time to think about how it works.  Students often find it helpful to look at smaller examples before stating the solution in general terms.

1 disk

• move 1 disk from A to C
•           

2 disks

• 1 disk solution to move top disk from A to B
• move remaining disk from A to C
• 1 disk solution to move 1 disk from B to C

3 disks

• 2 disk solution to move top 2 from A to B
• move disk from A to C
• 2 disk solution to move 2 from B to C

4 disks                                                                  

• 
• 3 disk solution to move top 3 from A to B   
• move disk from A to C                                
• 3 disk solution to move 3 from B to C         

We are now ready to describe the complete recursive algorithm for the Towers of Hanoi:

• Base Case: 1 disk
  •  Move 1 disk from peg A to peg C
• General Case:  2 or more disks
  1. Move top N-1 disks from peg A to peg B
  2. Move last disk from peg A to peg C
  3. Move top N-1 disks from peg B to peg C

There exist numerous links to explanations and online Towers of Hanoi games. Here are some we like:

• http://www.python-course.eu/towers_of_hanoi.php
• http://en.wikipedia.org/wiki/Tower_of_Hanoi
• http://www.mathsisfun.com/games/towerofhanoi.html
• http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm