Difference between revisions of "Towers of Hanoi"
|[checked revision]||[checked revision]|
Revision as of 09:06, 9 July 2014
- 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
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.
The problem can be stated as such:
Complete the definition of
towers_of_hanoiwhich prints out the steps to solve this puzzle for any number of
ndisks starting from the
startrod and moving them to the
endrod: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)
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.
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
towers_of_hanoi, what is the easiest base case to solve? What should the function do in that 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:
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
n to the
At this point, disk
n is free to move, so we can place it at the end:
And then, we just need to move the
n - 1 disks to the end as well:
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
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.
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:
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.