Towers of Hanoi

From CS 61A Wiki
Jump to: navigation, search
Purge this page if the LaTeX typesetting doesn't render.

Towers of Hanoi is a puzzle that involves three pegs and n disks. The each disk is of a unique size, with smaller disks always going on top of larger disks on a peg. At the beginning of the puzzle, all the disks are stacked on one starting peg from smallest (on the top) to the largest (on the bottom). The goal is to make the necessary valid moves to move the disks from the start peg to the desired end peg.

Valid moves are such that

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.


Problem

The problem can be stated as such:

Complete the definition of towers_of_hanoi which prints out the steps to solve this puzzle for any number of n disks starting from the start rod and moving them to the end rod:
def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game if we start
    with n disks on the start pole and want to move them all to the end pole.
 
    The game is to assumed to have 3 poles (which is traditional).
 
    >>> towers_of_hanoi(1, 1, 3)
    Move 1 disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move 1 disk from rod 1 to rod 2
    Move 1 disk from rod 1 to rod 3
    Move 1 disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move 1 disk from rod 1 to rod 3
    Move 1 disk from rod 1 to rod 2
    Move 1 disk from rod 3 to rod 2
    Move 1 disk from rod 1 to rod 3
    Move 1 disk from rod 2 to rod 1
    Move 1 disk from rod 2 to rod 3
    Move 1 disk from rod 1 to rod 3
    """
    "*** YOUR CODE HERE ***"
 
 
def move_disk(start, end):
    print("Move 1 disk from rod", start, "to rod", end)

Approach

Overview

When we approach a problem recursively, we need to try and break it down into a smaller version of the same problem. Just like a recursive factorial function utilizes the fact that $n!=n\cdot(n-1)!$ to make recursive calls, our approaches to other recursive problems should do something similar. We need a recursive definition, which tells Python how to recurse through this problem, and a base case, which tells Python where to stop recursing.

Base Case

So let's start with the base case. The base case should be a case where we do not need to make recursive calls to know what the answer is ($1!=1$, for factorial). In towers_of_hanoi, what is the easiest base case to solve? What should the function do in that case?

Recursive Case

Now what about the recursive case? Trying to figure out the algorithm to correctly move each disk is a bit difficult, so let's only deal with the nth disk, or the bottom-most one, and somehow have recursion deal with the other n - 1 disks. Here, we have the start of the problem:

Hanoi0.png

To move all the disks from start to end we need to eventually move disk n. But since we can only move the top-most disk of any tower, we have to first move all the n - 1 disks to the offset, so that later we can move disk n to the end:

Hanoi1.png

At this point, disk n is free to move, so we can place it at the end:

Hanoi2.png

And then, we just need to move the n - 1 disks to the end as well:

Hanoi3.png

At this point, the only thing that we may be unsure of is how to move the n - 1 disks from the start to the offset. But note exactly what towers_of_hanoi does. The function towers_of_hanoi prints the procedure of how to move n disks from start to the end.

And already, we've come across a smaller version of this problem! We need to move the n - 1 disks from start to the offset, which in itself is a towers_of_hanoi problem, only with a different destination, and one less disk. We encounter the problem again when after we move the nth disk, we need to move the n - 1 disks again to the end as well.

The Trick

Of course, we're not done defining towers_of_hanoi yet, but we know what the goal of it is anyways. Once we're finished, it should work as we had intended it to, so let's take a recursive leap of faith, and go ahead and make recursive calls to towers_of_hanoito move the n - 1 disks out of our way. The only thing that may be tricky is to figure out which peg is the "offset" peg. Consider the following:

start end offset
1 3 2
3 1 2
1 2 3
2 1 3
2 3 1
3 2 1

After a lot of thought, one might come up with offset = 6 - start - end. This is just an expression that matches the table above, so don't worry if you didn't come up with this.