#Move method hanoi towers how to

What this argument tells us is that once we know how to move a tower of height n-1, we can move a tower of height n. Once the top n-1 discs are sitting on peg 2, we move the largest disc to peg 3 and then transfer the n-1-tower from peg 2 to peg 3 in the same way as before - we've moved the whole tower of height n! The fact that the bottom disc keeps sitting on peg 1 all the way through makes no difference, as it is bigger than all the others anyway, so we can place any disc we want on top of it. Now we can move the top n-1 discs to peg 2 without ever placing a larger one onto a smaller one: we simply use the same method as we would if there were only n-1 discs in total. On peg 1, so that pegs 2 and 3 are empty. Now imagine that we have a tower of height n and that we know how to solve the game for a tower of height n-1. We've already seen that it's possible to move a tower of height one, two or three.

Our first task is to prove that it is possible to move a tower of any height (that is one made up of any number of discs) from one peg to another without breaking the rules. With n discs, in other words that there is no quicker way? The solution Can you express m n in terms of m n-1? Can you show that m n is in fact the minimum number of moves needed to solve the puzzle Write m n for the number of moves you need to solve the puzzle with n discs according to this recipe. Your proof now gives you a recipe for solving the puzzle for any number of discs. Now assume that you can move a tower of n-1 discs: does this help you to move a tower of n discs? If yes, then why does this prove that the puzzle can be solved for any number of discs? (A proof that uses this way of thinking is an example of the principle of We've already seen that the puzzle can be solved for n equal to 2 and 3. Hint: Suppose that you have n discs in total. But can you show that it is possible to move a tower consisting of any number of A little thought will show you that moving a tower of three discs is possible also. If you've only got two discs in total, then the puzzle is easy: move the top disc from peg 1 to peg 2, then move the bottom disc from peg 1 to peg 3, and finally move the smaller disc on peg 2 onto the larger disc on peg 3 - done.

you can only place a disc on a peg if either the peg is empty or if the discs already sitting there are larger than the disc you're about to place.

when you remove a disc from a peg you must place it on one of the other two pegs before you can move any other disc,.

The aim is to move the whole tower of discs onto another peg, subject to the following rules: Initially, all discs sit on the same peg in the order of their size, with the biggest disc at the bottom. It consists of three pegs and a number of discs of decreasing sizes. Then use rule 3 at every iteration to figure out which disk to move.The Towers of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883.

First, use rules 1 and 2 to figure out which direction every disk moves in. Using these rules, it's easy to write an iterative solution. If you start at all 0s, then you're done when you get to all 1s. then at each step, the highest bit that changes corresponds to the largest disk that moves. If you count in binary with a bit for each disk: 000 001 010 011 100. You start with all 1s, and replace every 2nd 1 with a 2. Rule 3 determines the pattern of which disk moves. RULE 3: Always move the biggest disk you can, in its proper direction. You want the largest disk to move only once, so that one determines the direction of all the other disks. This makes it easy to figure out which way the first move goes. Otherwise they move in the same direction. It also means that if the you have an even number of disks, then the largest and smallest move in opposite directions. That means that if disk 1 (the smallest) moves clockwise, then 1, 3, 5, 7. RULE 2: Alternate disks move in opposite directions. RULE 1: A single disk will move in only one direction - clockwise or counter-clockwise. Now, each time you move a disk, it's going to move either clockwise or counter-clockwise. Here's a different way to understand how the disks move in a Towers of Hanoi solution, that makes it easy to write an iterative solution:Īrrange the pegs in a triangle like this: A C The iterative solution is often more efficient, but requires a deeper insight. When a problem has both recursive and iterative solutions, the recursive solution is usually easier to formulate and understand.

Move method hanoi towers