Towers of Hanoi
From Math Images
| Towers of Hanoi |
|---|
Towers of Hanoi
- The Towers of Hanoi is a well known puzzle game based on a legend in which 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.
Contents |
Basic Description
The standard game begins with 3 towers, one of which (typically the leftmost) has some natural number, n, disks placed around it in increasing size from top to bottom, while the other towers start out empty. The goal of the game is to move all of the disks onto another tower (typically the rightmost), however only the top disk on any given tower can be moved, and disks may only be placed upon an empty tower or on top of a larger disk on another tower.Play the Game
You can play the game Towers of Hanoi right here! It doesn't support more than 10 disks, however.
A More Mathematical Explanation
The Recursive Solution
This game becomes more interesting when we try to figure out the quickest solution to any Towers of Hanoi game. Most often the easiest way to wrap one's head around this is the recursive solution, for which we will use a simple proof by induction to prove that not only is any game of Towers of Hanoi solvable, but also that they all have a formulaic minimum number of moves to solution. We begin with the base case of a game that has only 1 disk. This is easy, you simply move to disk once to any other tower and the game is complete in only 1 move. There is in fact no way to not solve the game with a minimal number of moves with only 1 disk as the only possible 1st moves solve the game. So our base case is solvable, thus we have to now complete our inductive reasoning through a general case. For this step, we have a k disk game and we want to solve it under the assumption that we can solve a k-1 disk game. Well, this is simple, as we have 3 towers to work with. First, we solve the k-1 game, which we know we can solve by assumption, then we move the kth (the largest of the disks) to the tower on which the other k-1 disks aren't on, then you solve the game by using the assumption that you can solve the k-1 game by moving the k-1 disks on top of the newly relocated kth disk. We can see that this will always work as the induction holds.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.


