Introduction: Write Code to Solve the Tower of Hanoi Puzzle
Q: What's the easiest way to get the sum of all whole numbers between 1 and 100?
A: First get the sum of all whole numbers between 1 and 99, then add 100.
Silly, right? This is actually an example of a powerful divide-and-conquer technique in computer programming known as "recursion." Recursion treats a computation task as a set of smaller, similar computations, with the next smaller computation being calculated, and then the next, and the next, until you get to a "base case" with a known answer. For the next step of the example above, to get the sum of whole numbers between 1 and 99, you simply sum the whole numbers between 1 and 98, then add 99. If you keep going down the chain, you will get to the base case of summing whole numbers between 1 and 1, which we know is 1.
A fun use of recursion is to write a program that can give you the solution to the Tower of Hanoi puzzle. That puzzle is shown in the image on this page. The goal is to move all disks from the first post to the third post. The rules of the puzzle are:
- You can only move one disk at a time from one post to another, which means at any given time, at most one disk can be off a post.
- You can move any disk to the second post as a resting area.
- Disks cannot be moved on top of a smaller disk.
How can this puzzle be broken down into smaller parts? As the images show, this 7-disk version of the Tower of Hanoi puzzle can be solved as:
- Solve the 6-disk version of the puzzle from post A to post B.
- Move disk 7 from post A to post C.
- Solve the 6-disk version of the puzzle again, this time from post B to post C.
For this instructable, I'll use JavaScript as the programming language so you can run this in a standard web browser. It helps to be familiar with some basic computer programming concepts, but even if you're not, hopefully this instructable will be interesting.
If you like this instructable, please vote for me in the Coded Creations contest before May 18, 2015. Thank you.
Let's start coding!
Step 1: Identify the Base Case
The simplest form of the Tower of Hanoi puzzle has only 1 disk. To solve a 1-disk Tower of Hanoi, simply move the disk from post A to post C. Done. In pseudo-code (i.e., a "plain English" way to express what a computer program is doing), this will look like:
If the disk you're about to move is disk 1, i.e., the smallest disk (or the only disk), then move it from post A to post C.
If we generalize the above, we replace "post A" with "the post it currently sits on," and we replace "post C" with "the post we want it to end up on."
The JavaScript looks like (note that I've generalized the reference to the start post and the destination post, this is important as described in the next step):
if (disk == 1) { // "disk" is the disk number, where 1 represents the smallest disk
document.write("Move disk " + disk + " from post " + start + " to post " +
destination + ".<br/>";
// "start" represents the starting post, which changes depending on which disk
// you're moving
// "destination" represents the destination post, which also changes depending
// on which disk you're moving
}
Step 2: Code the Recursive Pattern
To solve for N disks, we need to be able to solve for N-1 disks. This is where the recursion comes in. As part of this plan, you want to write code that applies to a different number of disks for the puzzle, as well as different start and destination posts.
The pseudo-code for that looks like:
Solve for N-1 disks, but move them from post A to post B. Move the largest disk (disk N) from post A to post C. Solve for the N-1 disks again, and move them from post B to post C.
I specifically referred to post A, post B, and post C above, but the code needs to be generalized because depending on the disk, the start post and destination posts will be different. If you think about it, we're solving the puzzle 3 times:
- Moving N-1 disks from post A to post B
- Moving N-1 disks from post B to post C
- Moving N disks from post A to post C
So you need a generalized program that will let you tell it what the start and destination posts are. What's interesting is that you're not really writing a lot of code, which is a big part of the appeal of recursion. You simply describe in the program how to break a computation into smaller pieces, and the computer does the rest.
The detailed pseudo-code looks like:
If the disk you're moving is the smallest,
then move it from the start post to the destination post.
Otherwise...
Start again at the top of this code with a new set of inputs:
Use one fewer disk.
Use the same start post.
Use the staging post as the destination post.
Move the largest disk from the start post to the destination post.
Start again at the top of this code with a new set of inputs:
Use one fewer disk.
Use the staging post as the start post.
Use the same destination post.
Here's how the JavaScript code looks:
function solve_tower_of_hanoi(disk, start, destination, staging) {
if (disk == 1) {
// base case of 1 disk, we know how to solve that
document.write("Move disk 1 from post " + start + " to post " + destination +
".<br/>");
} else {
// first solve for all except the last disk
solve_tower_of_hanoi(disk - 1, start, staging, destination);
// now move the last disk
document.write("Move disk " + disk + " from post " + start + " to post " +
destination + ".<br/>");
// now solve for the remaining disks
solve_tower_of_hanoi(disk - 1, staging, destination, start);
}
}If you're not a programmer, let me explain that the code above is wrapped into a "function" which lets you run the same code with different inputs. You can now tell the program how many disks you have in your puzzle, as well as which posts are the start, destination, and staging posts. The function is also the basis for being able to run recursion, in which the same code is run again and again but with different inputs (inputs are also known as "parameters" or "arguments" in programming lingo).
Step 3: Put It All Together and Run It
A very simple HTML page with the JavaScript program looks like this:
<html>
<body>
<script>
// call the function to start solving the puzzle for 7 disks
solve_tower_of_hanoi(7, "A", "C", "B");
function solve_tower_of_hanoi(disk, start, destination, staging) {
if (disk == 1) {
// base case of 1 disk, we know how to solve that
document.write("Move disk 1 from post " + start + " to post " + destination +
".<br/>");
} else {
// first solve for 6 disks (i.e., disk - 1)
solve_tower_of_hanoi(disk - 1, start, staging, destination);
// now move the 7th disk
document.write("Move disk " + disk + " from post " + start + " to post " +
destination + ".<br/>");
// now solve for the 6 disks from post B to post C
solve_tower_of_hanoi(disk - 1, staging, destination, start);
}
}
</script>
</body>
</html>
The code above is in the first attached file, which you can save to your computer (but remove the .txt from the end of the filename before you save it), then open with a web browser. If you want to solve the puzzle for any other number of disks, edit the file using a text editor (like "notepad" on PCs) and change the "7" on line 5 to the number of disks you want.
Also attached is a slightly more sophisticated version of this program that lets you type in the number of disks directly in the web page.
Step 4: Conclusion
The Tower of Hanoi puzzle is a great example of how recursion can more easily solve a problem. If you were to try to code a solution to Tower of Hanoi by other means, it would be a lot more complicated and would take a bit more thinking.
Recursion can be used for a variety of tasks including computations, sorting values, and quickly finding a value in a sorted list. And while it is often not the best method for programming, as it is often slow and resource intensive on the computer compared to other coding methods, it is a great learning tool for thinking about how to break down a problem into manageable pieces. And the ability to break a problem into smaller pieces is a valuable skill for computer programming.