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

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 using a recursive solution. We will use a simple proof by induction to prove that not only is any game of Towers of Hanoi solvable, but also that there is a minimum number of moves to solution. The Formula to calculate the number of moves is this:

The 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 k^th (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 k^th disk. We can see that this will always work as the induction holds.

Now we know that we can at least solve every game, but now we need to calculate the number of moves it takes to solve any given game.