Project Notes

Solving the Tower of Hanoi puzzle is a classic programming project. The puzzle comprises three pegs and a number of disks, each a different size and having a hole in the middle so that it can be placed on the peg. The puzzle starts with all of the disks on one peg with the smallest on the bottom and continually smaller disks stacked on top. The object is to move all of the disks to another peg. The rules are simple: at any time you may move one top disk to another peg, but you may never place a larger disk on a smaller disk.

To solve this puzzle, it is best to break down the problem into smaller and smaller pieces. Moving the smallest disk is easy: pick it up and put it on the target peg. Moving a stack of 2 disks is not hard. Move the small disk to the spare peg, then move the large disk to the target peg, then move the small disk on top of the large disk on the target peg. To move a stack of 3 disks, move the top two disks to the spare peg (in the way I just described), then move the largest disk to the target peg, then move the remaining 2 disks to the target peg on top of the largest disk (again in the way I just described). To move a stack of 4 disks, move the top 3 to the spare peg, move the largest to the target peg, and move the remaining 3 on top of the large one. Larger stacks, of 5, 6, 7, and up, are solved in the same way.

Once you understand this solution, writing a program to solve this puzzle using recursion is easy. To do this, you create a procedure that moves n disks. The procedure is implemented by calling itself to move n-1 disks, then moving the bottom disk, then moving the n-1 disks again. The procedure keeps calling itself with a progressively smaller number of disks until it is asked to move one disk, which is an easy case.

That said, solving the Tower of Hanoi puzzle in Scratch is challenging because Scratch has no procedure calls or any built in mechanism for recursion. This project does in fact use recursion to solve the puzzle. It does this by using some lists as procedure call stacks.

There are a few other Tower of Hanoi projects, including some that also solve the puzzle. Unlike the other ones I have seen, which use a non-recursive but confounding pattern, this project uses a truly recursive solution. Another interesting feature of this project is that all of the sprites, each representing a disk, are exactly the same in terms of scripts and costume. During an initialization step each of the disks takes on a unique size and puts itself on the proper place on the initial peg. If you download this project, you can adjust the number of disks by simply deleting or duplicating any sprite.