The Tower of Hanoi

mikau · 2007-07-10 20:15:39

I've been busying myself with lots of brain teasers over the summer, trying to conquer as many as possible (solved the rubiks cube! ) and today i decided to tackle the Tower of Hanoi. My self assigned task was to write a program that could solve the tower with any number of disks. I had heard recursion was key to solving the problem so i figured it out pretty quick. Anyway, i was suprised to find there seems to be no thread specifically for the tower of hanoi yet. There appears to be a pretty cool solution animation here, but it doesn't say much about the algorithm.

Since I'd been wrapping my head around it today, i decided to write a short article about the solution, and (hopefully ) the applet game (http://www.mathsisfun.com/games/towerofhanoi.html) could link to this thread for discussion about the solution. I think its a pretty interesting puzzle and worthy of some brief attention.

Anyways, here's what I wrote. Tell me what you think. This assumes you know the rules of the game. I tried to make it easy for anyone to understand.

How to solve The Tower of Hanoi for any number of disks

If we consider a tower with 8 disks

and we wanted to move all the disks to the third needle,
We could do the following:

A. Transfer all the disks directly above the 8th disk to the 2nd needle.

B. Move the bottom disk (which is now free to move) to the 3rd needle

C. Transfer the 7 disks on the 2nd needle onto the 3rd needle!

Well that works fine, except now we have to figure out, how do we first transfer the 7 disks from needle 1 to needle 2 in step A, and second, how do we transfer the 7 disks from needle 2 to needle 3 in step C?

Interestingly, we are now met with the same question of how to transfer a pile of disks from one needle to another! Are we back where we started? Are we going in circles?

Actually we're not. Because we've reduced the problem of an 8 disk tower to the problem of a 7 disk tower. With the same reasoning, we could conclude that we could solve a 7 disk tower
if we knew how to solve 6 disk tower. And 6 if we knew 5 and in general, we can solve an 'n' disk tower if we can solve an 'n-1' disk tower.

If we continue to reduce the problem above, the question ultimately becomes, how do you transfer a tower with 1 disk from one needle to another?
Simple. Pick it up and put it there!

We therefore, know how to solve a tower with 2 disks. Knowing this, we can solve a tower with 3 disks so we can now solve 4. And then 5 and in fact, if
we don't loose track of what we're doing, we can solve as huge a tower as we want, just from knowing how to solve a 1 disk tower!

A recursive Nature

The reason this problem is most interesting is that the solution is recursive. In otherwords, the solution is made up of smaller versions of the solution itself! We can use this property to solve the problem if, and only if, the problem eventually becomes so small and simple, that we can solve it directly, that is, without breaking it up into even smaller pieces.
In a recursive algorithm, this is known as the 'base case'. Here, the base case was solving a 1 disk tower. Because we can reduce the problem to the base no matter how many disks we use, the solution works for any number of disks!

Recursive problem solving is a powerful tool frequently employed by computer scientists and allows them to solve some extremely difficult problems with relative ease, and fewer lines of code!

How many moves?

How many moves will it take to solve The Tower of Hanoi using this method?

If we consider a tower with n disks, let S(n) be a function that gives the number of moves to solve an 'n' disk tower. It would follow that S(n) = 2S(n-1) + 1.
That's becuase, to solve an n disk tower, we have to solve an n-1 disk tower(S(n-1) moves), move one disk, (+1 move) and then solve another n-1 tower. (+S(n-1) moves)

What function satisfies the equation S(n) = 2S(n-1) + 1?
It turns out to be S(n) = 2^(n) - 1. (plug it into the equation and you'll see that it works)
This basically means that every time we add a disk, the number of moves required to solve actually doubles.

So how many moves would it take to solve an 8 disk tower? 2^8 - 1 = 255 moves.

Want to try solving a 64 disk tower? Don't bother. At 1 disk/sec it would take you about 584 billion years to finish!

Last edited by mikau (2007-07-10 20:44:15)

mikau · 2007-07-10 20:33:41

So whadja think? I'd be most grateful for any comments, corrections, or suggestions on how to make this better.

luca-deltodesco · 2007-07-10 21:05:56

yes i see what you mean, i just tried playing the game, started with stack of 3,then 4, then i did 8 (although it took a while) and yes, it reduces to moving around smaller and smaller stacks of blocks

mikau · 2007-07-10 21:13:49

yep. It becomes evident that it has recursive behavior just from playing it, (assuming you're reflecting on your actions) the program i wrote could tell you how to solve a tower with any number of disks, prints instructions to a text file. Lol, but I calculated that if I were to output the solution to a 64 disk tower to a file, based on how it was formatted, at 8 bits per character, the file would be about 6.5 trillion gigabytes in size! I figured... better not try that...

Ricky · 2007-07-10 21:56:10

You're right, it is recursive in nature. It's also exponential. Can you prove each of these? That is, what is the theoretically fastest possible way to solve TOH, and how fast is the recursive algorithm in comparison to this?

mikau · 2007-07-11 14:01:53

hmm... I've never actually done a 'fastest way to solve' problem and pretty much have no idea where to begin. Can you give me some hints?

Ricky · 2007-07-11 16:37:34

To me, this is where comp sci gets fun.

I'm not quite sure what hints to give and what would be too much. But basically the way to go about doing this is, no matter what algorithm you use, what _must_ be done?

First step: Show that f(n) > f(n-1), where f is just the function on the minimal number of steps required to solve TOH.

Edited to add: This first step isn't really needed, but it gets you thinking along the same lines that are used to solve the problem.

mikau · 2007-07-11 19:12:08

thanks, ricky! I'll work on it!

Anthony.R.Brown · 2007-07-11 23:50:29

It's a Very Simple Problem to Solve! the same Pattern swapping method! works with any amount of Disks!..

--------------------------------------------------------------------------------------------------------------
Genius Is Noticed! But Refused Acceptance! By Persons With Academic liabilities! .....................

krassi_holmz · 2007-07-12 01:52:37

I was on a programming school lately.
One of the themes was TOH - someone wrote the program and ran it and it generated 20GB output file!

mikau · 2007-07-12 06:41:48

hahaha. Yeah, i'm not suprised. Do you know how tall the tower was?

mathsyperson · 2007-07-12 07:44:25

I'd estimate somewhere around 30 blocks high. Maybe a few more.

mikau · 2007-07-12 07:48:35

For anyone who cares, here's the the method definition in java to solve the tower (without printing the output to a file). I created two simple classes, HanoiDisk and HanoiPipe, and you don't see their definitions here, but their workings are pretty intuitive.

// method to move all the disks from 'fromPipe' to 'toPipe'
public static void hanoi(int numOfDisks,  HanoiPipe fromPipe, HanoiPipe middlePipe, HanoiPipe toPipe) 
{

	if (numOfDisks > 1)
	{
		hanoi(numOfDisks-1, fromPipe, toPipe, middlePipe);
		HanoiPipe.transferDisk(fromPipe, toPipe);
		hanoi(numOfDisks-1, middlePipe, fromPipe, toPipe);
	}
	if (numOfDisks == 1)
	{
		HanoiPipe.transferDisk(fromPipe, toPipe);			
	}
}

you gotta love how short and simple recursive algorithms are!

mikau · 2007-07-12 10:50:46

Okay, ricky. I think I've sort of got it.

I base it on two axioms. I might call them theoems because i attempt to proove them, but they're based mostly on what i consider to be obvious and obvious things are hardest to proove!

Anyway, here we go!

vanishing disk axiom
if you wish to move an n disk tower from needle a to needle b, and there is a larger disk either beneath the tower at needle a, or on b or c, and you want the largest disk to end up in its original location, The fastest way to move the tower is equal to the fastest way to move the tower where no larger disk is present.
Justification: all the existing disks are smaller than the larger disk, and thus any disk can be placed on it. The larger disk is thus equivilent to a floor except it can be moved.
Moving this largest piece has no effect on the other pieces as it cannot be placed ontop of either. If it were moved to another empty needle, it would have to be moved back later and this would waste 2 steps.

single tower axiom.
the fastest way to move a one disk tower from needle a to needle c is to move it there directly.
justification: we can either begin the move by picking up the disk and putting it where it was, moving it to needle 2, or moving it to needle 3. The first method must take greater than 1 move to complete, likewise for the second, the third takes one move, thus it must be the fastest.

Now I'm going to attempt to proove my recursive algorithm is the fastest.

Proof my recursive algorithm is the fastest!

The bottom disk must be moved to the base of needle 3 before the tower can be completed. We can either do this first, or do something else first, and then attempt to move the base disk from its location at that time, to needle 3.
if you wish to move the base disk from needle 1 to needle 3
Whether we seek to move the base disk immediately, or do it later, we have to end up with all the other disks on needle 2, and needle 3 empty. (being the largest disk we cannot place it on needle3 unless it is empty) This means, we could not possibly set up the disks in some fashion such that after moving the base disk, we could solve it quicker than had we arranged it differently before the move. (because it could not possibly have been arranged differently) Therefore, our only concern is to get into that unique scenario as quickly as possible.

if you wish to move the base disk from needle2 to needle 3
this would require we first move the base disk to needle 2 which means all other disks be transfered to needle 3, which is equal to the above problem with the needles relabled. We must then move move the base disk from needle 2 to needle 3. Therefore, this choice of action must take more moves than first moving the base disk from needle 1 to needle 3.

So we have concluded we must first transfer the base disk from needle 1 to needle 3 and it follows we must first move the n-1 disks from needle 1 to needle 2 in the fastest way possible. By the vanishing disk axiom, we can use the fastest way to move an n-1 disk tower from needle a to needle b with no other disk present.

Assuming we know how to do this, the remaing problem is simply, the fastest way to transfer the n-1 disks on needle 2 to needle 3. Again by the vanishing disk axiom, we can use the fastest way to move an n-1 disk tower from needle b to needle c with no other disk present.

We are met with the same problem twice with relabeled needles.

The fastest way to move an n disk tower from needle a to needle c is therefore recursively defined as:

move the n-1 disk tower from needle a to needle b in the fastest way,
move the nth disk from needle a to needle c
move the n-1 disk tower from needle b to needle c

We therefore know the fastest way to solve an n disk tower if we know the fastest way to solve an n-1 disk tower, and thus if we know the fastest way to solve an n disk tower, we can solve an n+1 disk tower.
We know the fastest way to solve a 1 disk tower by the single tower axiom. therefore we can determine the fastest wayto solve a 2 disk tower, and from that a 3 disk tower, and thus
the above algorithm is the fastest way to solve the tower.

Last edited by mikau (2007-07-12 11:09:25)

Ricky · 2007-07-12 11:29:47

You are essentially correct. However, you overcomplicated it a bit. I was planning on you answering the first question I posed, and then leading you in the right direction towards the solution, but this works just as well.

Let f(n) be the fastest way to solve a TOH with n disks.

As a rule of the game, the largest disk must end up on the bottom of C. To place it there, there must be no disks on C. To move the bottom disk, there must be no disks on top of it (WLOG, we'll say it's on A). As a rule of the game, no disks may also be below the largest one. Thus, all n-1 disks must be on B.

The fastest way to move all n-1 disks from A to B is f(n-1), by definition of what f is. The fastest way to move the largest disk to C is 1. The fastest way to move the n-1 disks from B to C is again by definition, f(n-1). Thus, the total of f(n) = 2*f(n-1) + 1.

Now find a close form solution for the minimum number of movements.

A much better way to prove your "single tower axiom" is to just simply state: Movements must be in natural numbers, we can move it in 1 step, thus, by the well ordering principle of the natural numbers, this is the least number of movements possible. But typically, I would honestly write, "It's obvious...".

It's very important to see how I started with only the premises of the rules and used nothing but logic to come to my conclusions. I didn't use common sense or anything of that nature.

Do you like these? I have tons more.

mikau · 2007-07-12 13:06:41

yes I would like to see more! but not yet. I'm not done with this one.

Your proof is what occured to me at first but i was kind of paranoid about making assumptions. So I may have overcomplicated as you said.
Still,

yes we have to move the nth disk to C at SOME point, but when I did it I felt I was assuming that must be the first step and this concerned me. Don't you have to proove that?

and second, why not try moving the the nth disk to B before C? its quick to show why but doesn't it need to be shown still?

I'm not really used to doing proofs so i might be stating the obvious too much.

Last edited by mikau (2007-07-12 13:21:16)

Ricky · 2007-07-12 13:33:38

yes we have to move the nth disk to C at SOME point, but when I did it I felt I was assuming that must be the first step and this concerned me. Don't you have to proove that?
and second, why not try moving the the nth disk to B before C? its quick to show why but doesn't it need to be shown still?

This is all covered by the concept of "fastest".

The first part was proving that there is one specific state the tower had to be in to move the largest disk to C. That state is the big disk on A, all other disks on B. Note that 'A' and 'B' are just labels, it could actually be big disk on B and all others on A, it doesn't matter. You'll typically hear this referred to as 'Without loss of generality', or WLOG.

But the key thing is it has to be in this state to move the big disk to C. Because we have to move the big disk to C, our solution, must at one point reach this state.

So the question becomes: What is the quickest way to reach this state from the starting conditions? Answer: f(n-1).

mikau · 2007-07-12 13:57:08

okay. Yeah i think i was more or less questioning my logic and afraid i was assuming so i appeased myself by stating the obvious.

hmmm... okay, I wouldn't mind seeing another now.

Ricky · 2007-07-12 15:25:10

New thread for a new topic.

Anthony.R.Brown · 2007-07-13 23:44:37

Now try doing the Tower of Hanoi Problem with Different size Disks! on more than Three Posts!

--------------------------------------------------------------------------------------------------------------
Genius Is Noticed! But Refused Acceptance! By Persons With Academic liabilities! .....................

Last edited by Anthony.R.Brown (2007-07-13 23:48:45)

luca-deltodesco · 2007-07-15 09:49:52

Do you even know how this game works? Adding more posts is completely redundant. And what do you mean different sized discs? they ARE different.

Ricky · 2007-07-15 10:07:53

Adding more posts is completely redundant.

Not entirely. It changes the problem dramatically and makes analysis of the run time much more complicated.

mikau · 2007-07-15 10:14:46

It changes the problem dramatically and makes analysis of the run time much more complicated.

it does? Can't we just ignore all but three? There's no rule about not being able to move a disk more than one post away.

Ricky · 2007-07-15 10:49:46

Can't we just ignore all but three?

Certainly. But what's the fastest way to do it?

Here's an easier question: TOH with 4 pegs, using my exact logic from before, come up with a faster way to do it than with 3 pegs.

luca-deltodesco · 2007-07-15 10:50:09

actually, i gave it more thought and it can change things, for example: 5 or more sticks, n=4, you can do it in 7 steps instead of 15 i think it is for 3 sticks, since it removes the need to rearrange things to allow you to move discs around.

My point remains for the different sized discs though ^^

Math Is Fun Forum

#1 2007-07-10 20:15:39

The Tower of Hanoi

#2 2007-07-10 20:33:41

Re: The Tower of Hanoi

#3 2007-07-10 21:05:56

Re: The Tower of Hanoi

#4 2007-07-10 21:13:49

Re: The Tower of Hanoi

#5 2007-07-10 21:56:10

Re: The Tower of Hanoi

#6 2007-07-11 14:01:53

Re: The Tower of Hanoi

#7 2007-07-11 16:37:34

Re: The Tower of Hanoi

#8 2007-07-11 19:12:08

Re: The Tower of Hanoi

#9 2007-07-11 23:50:29

Re: The Tower of Hanoi

#10 2007-07-12 01:52:37

Re: The Tower of Hanoi

#11 2007-07-12 06:41:48

Re: The Tower of Hanoi

#12 2007-07-12 07:44:25

Re: The Tower of Hanoi

#13 2007-07-12 07:48:35

Re: The Tower of Hanoi

#14 2007-07-12 10:50:46

Re: The Tower of Hanoi

#15 2007-07-12 11:29:47

Re: The Tower of Hanoi

#16 2007-07-12 13:06:41

Re: The Tower of Hanoi

#17 2007-07-12 13:33:38

Re: The Tower of Hanoi

#18 2007-07-12 13:57:08

Re: The Tower of Hanoi

#19 2007-07-12 15:25:10

Re: The Tower of Hanoi

#20 2007-07-13 23:44:37

Re: The Tower of Hanoi

#21 2007-07-15 09:49:52

Re: The Tower of Hanoi

#22 2007-07-15 10:07:53

Re: The Tower of Hanoi

#23 2007-07-15 10:14:46

Re: The Tower of Hanoi

#24 2007-07-15 10:49:46

Re: The Tower of Hanoi

#25 2007-07-15 10:50:09

Re: The Tower of Hanoi

Board footer