# Towers of Hanoi

(Difference between revisions)
 Revision as of 14:45, 24 May 2013 (edit)← Previous diff Revision as of 17:45, 24 May 2013 (edit) (undo)Next diff → Line 2: Line 2: |ImageName=Towers of Hanoi |ImageName=Towers of Hanoi |Image=10_Ring_Hanoi.jpg |Image=10_Ring_Hanoi.jpg - |ImageIntro=The Towers of Hanoi is a well known puzzle game based on a Hindu legend. According to the story, priests of the Hindu god Brahma were instructed to move 64 golden disks from one of 3 poles to another, and when they completed it the world would end. However, whether the game was inspired by the legend, or the other way around, is unknown. + |ImageIntro=The Towers of Hanoi is a well known puzzle game publicized in 1883 by Édouard Lucas, a French mathematician. According to the legend brought forth by Lucas, priests of the Hindu god Brahma were instructed to move 64 golden disks from one of 3 poles to another, and when they completed it the world would end. - |ImageDescElem=The standard game begins with 3 poles, one of which (typically the leftmost) has some whole number, k, disks placed around it in increasing size from top to bottom, while the other poles start out empty. + |ImageDescElem=The standard game begins with 3 poles, one of which (the starting pole) has some natural number, k, disks placed around it in increasing size from top to bottom, while the other poles start out empty. - :'''Goal''': Move all k disks from the start tower (typically the leftmost) to the specified end tower (typically the rightmost), following these rules: + :'''Goal''': Move all k disks from the start pole (typically the leftmost) to the specified end pole (typically the rightmost), following these rules: :*Only one disk may be moved at one time. :*Only one disk may be moved at one time. Line 11: Line 11: :*Each disk must be placed on a larger disk. :*Each disk must be placed on a larger disk. - To fully understand the end of the world legend, one must understand the relationship between the number of disks and the amount of moves. As it turns out, this relationship is [[Exponential Growth|exponential]]; if the priests move one disk per second, then they would need 18,446,744,073,709,551,615 seconds, or 584.54 billion years, to complete the game. Given that this is about 58.5 times the life span of the Sun, the legend overestimates the amount of time we have until the world ends (unless we can someday live without the Sun). + To fully understand the end of the world legend, one must understand the relationship between the number of disks and the amount of moves. As it turns out, this relationship is [[Exponential Growth|exponential]]; if the priests move one disk per second, then they would need 18,446,744,073,709,551,615 seconds, or 584.54 billion years, to complete the game. Given that this is about 58.5 times the life span of the Sun, the legend probably overestimates the amount of time we have until the world ends (unless we can leave the Earth before the Sun expands too much). ===Play the Game=== ===Play the Game=== You can play the game Towers of Hanoi right here! This applet will help you understand how the game works. {{Hide|1= You can play the game Towers of Hanoi right here! This applet will help you understand how the game works. {{Hide|1= - + }} - }} + ===Example of Solving the Game=== ===Example of Solving the Game=== Line 44: Line 43: Thus our ideal minimum function is a plausible solution to any Towers of Hanoi game. Thus our ideal minimum function is a plausible solution to any Towers of Hanoi game. - ===The Non-Recursive Equation=== + ===The Explicit Formula=== - We will show by [[Induction|induction]] that the non-recursive equation is + We will show by [[Induction|induction]] that the explicit formula is :$T_k=2^k-1\text{, for }k\in\mathbb{Z}_+$ :$T_k=2^k-1\text{, for }k\in\mathbb{Z}_+$ Line 68: Line 67: Assuming that the Sun has a life span of 10 billion years, the time predicted by the legend is $585.54\div10\approx58.5$ times longer than the Sun's lifespan. Assuming that the Sun has a life span of 10 billion years, the time predicted by the legend is $585.54\div10\approx58.5$ times longer than the Sun's lifespan. - |WhyInteresting=While legend says that the Towers of Hanoi originated from an Indian temple, no one is actually sure of the game's origin. A French mathematician named Édouard Lucas introduced the game in 1883, and most sources point to him as the inventor of the game. + |WhyInteresting=Towers of Hanoi is a popular example in introductory computer science courses; programming it is relatively simple but not trivial. The recursive nature of the game teaches recursion, while the simple interface of the game introduces basic graphics processing. In addition, the game's exponential solution shows why computer scientists dread exponential time; it takes far long to compute. Assuming the average computer can do 100 million operations per minute, then solving Towers of Hanoi with 64 disks would take the computer - + - Towers of Hanoi has interesting implications in computer science. To solve a game with k disks, we need at least $2^k-1$ moves, which is an [[Exponential Growth|exponential]] relationship. This indicates that the time required to solve the game will drastically increase as the number of disks increase. In computer science, good algorithm times are usually polynomial and logarithmic. Exponential times, however, are horrible for programming. Even with only 64 disks, the game requires 584.54 billion moves. Assuming the average computer can do 100 million operations per second, then it will need 5845.4 seconds, or 97.42 minutes, to solve the game. If we try to solve the game with any more disks, we would need to start using supercomputers to solve it within reasonable times. + - + - + |AuthorName=WikiBooks User GeniXPro |AuthorName=WikiBooks User GeniXPro

## Revision as of 17:45, 24 May 2013

Towers of Hanoi
The Towers of Hanoi is a well known puzzle game publicized in 1883 by Édouard Lucas, a French mathematician. According to the legend brought forth by Lucas, priests of the Hindu god Brahma were instructed to move 64 golden disks from one of 3 poles to another, and when they completed it the world would end.

# Basic Description

The standard game begins with 3 poles, one of which (the starting pole) has some natural number, k, disks placed around it in increasing size from top to bottom, while the other poles start out empty.
Goal: Move all k disks from the start pole (typically the leftmost) to the specified end pole (typically the rightmost), following these rules:
• Only one disk may be moved at one time.
• Each move consists of moving the top disk of one rod onto the top of another rod.
• Each disk must be placed on a larger disk.

To fully understand the end of the world legend, one must understand the relationship between the number of disks and the amount of moves. As it turns out, this relationship is exponential; if the priests move one disk per second, then they would need 18,446,744,073,709,551,615 seconds, or 584.54 billion years, to complete the game. Given that this is about 58.5 times the life span of the Sun, the legend probably overestimates the amount of time we have until the world ends (unless we can leave the Earth before the Sun expands too much).

### Play the Game

You can play the game Towers of Hanoi right here! This applet will help you understand how the game works.

If you can see this message, you do not have the Java software required to view the applet.

### Example of Solving the Game

Solving Towers of Hanoi with 4 disks.

# A More Mathematical Explanation

## The Recursive Solution

This game becomes more interesting when we try to figure out the quickest [...]

## The Recursive Solution

This game becomes more interesting when we try to figure out the quickest solution to any Towers of Hanoi game. We will first reason through the ideal minimum amount of steps to solve a game with k-disks, then provide an algorithm that requires the same amount of moves as this ideal minimum. Define $T_k$ to be the minimum amount of moves needed for k disks. It is obvious that:

$T_0=0$ and $T_1=1$

Assume that we know $T_{k-1}$ is true. Note that to move the kth(bottom) disk, we must first move the top k-1 disks. In addition, we must move the kth disk at least (and hopefully only) once. Finally, the top k-1 disks must be placed on top of the kth disk at some point to complete the game. Thus, the ideal recursive function for $T_k$ is:

$T_k=T_{k-1}+1+T_{k-1}=2T_{k-1}+1$

Now we will provide an algorithm that requires the same amount of steps as $T_k$. Since $T_0$ and $T_1$ do not change, we can assume that the (k-1)th game is solvable. One algorithm to solve the kth game is as follows:

1. Move the top k-1 disks to Pole B (assuming we start on Pole A and end on Pole C).
2. Move the kth disk to Pole C.
3. Move the k-1 disks on Pole B to Pole C, on top of the kth disk.

The total steps for this are:

$T_{k-1}+1+T_{k-1}=2T_{k-1}+1=T_k$

Thus our ideal minimum function is a plausible solution to any Towers of Hanoi game.

### The Explicit Formula

We will show by induction that the explicit formula is

$T_k=2^k-1\text{, for }k\in\mathbb{Z}_+$

The base case is satisfied:

$T_0=2^0-1=1-1=0$ as desired.

Assume the (k-1)th case holds. Then

$T_k=2T_{k-1}+1=2(2^{k-1}-1)+1=2(2^{k-1})-2+1=2^k-1$

Thus we have shown the non-recursive equation holds for any Towers of Hanoi game with k disks.

## Back to the Legend

Now that we have the equation to determine the amount of moves needed for any number of disks, we can verify the numbers listed in the Basic Description. A Towers of Hanoi game with 64 disks will take:

$T_{64}=2^{64}-1=18,446,744,073,709,551,615\text{ moves}$

If the priests move 1 disk per second, then they will need:

$18,446,744,073,709,551,615\text{ seconds}=\left(\frac{1\text{ minute}}{60\text{ seconds}}\right)=\left(\frac{1\text{ hour}}{60\text{ minutes}}\right)=\left(\frac{1\text{ day}}{24\text{ hours}}\right)=\left(\frac{1\text{ year}}{365.25\text{ days}}\right)\approx584.54\text{ billion years}$

Assuming that the Sun has a life span of 10 billion years, the time predicted by the legend is $585.54\div10\approx58.5$ times longer than the Sun's lifespan.

# Why It's Interesting

Towers of Hanoi is a popular example in introductory computer science courses; programming it is relatively simple but not trivial. The recursive nature of the game teaches recursion, while the simple interface of the game introduces basic graphics processing. In addition, the game's exponential solution shows why computer scientists dread exponential time; it takes far long to compute. Assuming the average computer can do 100 million operations per minute, then solving Towers of Hanoi with 64 disks would take the computer