Blogs
Rebuilding the Tower of Hanoi
Sometimes seemingly serial computations may be coded with parallel algorithms if you can figure out how to present the final results in the proper order.
The Tower of Hanoi is a puzzle that consists of three pegs and a set of disks. Each disk has a different diameter and a hole in the middle so that the disk can fit onto any of the pegs. The initial puzzle setup has two of the pegs empty and all the disks on the third peg (source) in monotonically decreasing order of diameter from bottom to top, which forms a structure that is reminiscent of a tower. The goal of the puzzle is to move the tower from the source peg to a specified peg (destination) using the other peg to temporarily hold disks. The two rules of the Tower of Hanoi puzzle are that only one disk at a time can be moved from the top of a stack of disks on a peg to some other peg, and disks with larger diameter cannot be placed on top of smaller diameter disks.
French mathematician Edouard Lucas developed the puzzle in 1883. He also created the myth for his puzzle that claimed monks have been working non-stop on a 64-disk version from the beginning of time. Once they have solved this problem, the tower will crumble and the world will end. It's a good story and, I'm sure, it helped to promote the puzzle, but everyone knows that the world ends at 03:14:07 on Tuesday, January 19, 2038.
A programmed solution can be implemented using recursion in a most elegant way. (Again with the recursion? Just one more to finish up, I swear. I'll start my next post with something completely different.) Here's one way to code up a solution.
void tower(char source, char dest, char temp, int level)
{
if (level > 0) {
tower(source, temp, dest, level-1);
printf("Move from %c to %c\n", source, dest);
tower(temp, dest, source, level-1);
}
else
printf("Move from %c to %c\n", source, dest);
}
. . .
tower('A', ‘C', 'B', numDisks-1);
. . .
I've used single characters to denote the pegs ('A' is the initial source peg, 'C' is the final destination, and 'B' is the temporary peg). The recursion is halted when the level parameter reaches zero. This corresponds to the source peg having one disk remaining on it, so the code simply prints the move of a disk from the source to the destination peg without further recursive calls. As you can see, the purpose of the code is to print out the set of instructions that can be mechanically followed by someone trying to solve the puzzle in the fewest moves.
 |
To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy. |
