Towers of Hanoi - Part 1


Collapse Content

The Puzzle

The Towers of Hanoi is a classic puzzle with 3 pegs and multiple disks of different sizes. The goal of the puzzle is to move all the disks from the first peg to the the third peg according to the following rules:

  1. Only one disk can be moved at a time.
  2. You can only move the top disc in a stack.
  3. No disk may be placed on top of a smaller disk.

Try out the game below with 3 disks:


Finding an Algorithm

Once you've solved the puzzle with 3 disks, try again with 4 disks or 5 disks. Can you figure out a general strategy, or algorithm, for solving this puzzle with any number of disks?

To reach a general solution, first break down the problem into its simplest form. We'll start with only one disk and work our way up.

Case 1: What do you do when there's just one disk on a starting peg and you need to get it to the goal peg?

Answer: Move the disk to the goal peg.

That wasn't very difficult, but it's the fundamental step. Now for Case 2.

Now that you have the Algorithm for 2 disks, write a program to solve moving 2 disks from one peg to another.

Challenge

How do you solve the problem when there are just 2 disks on a starting peg and you need to move them to the goal peg?

Describe the steps you would take below and then click Submit.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Challenge

Above, you moved disks from Peg 1 to Peg 3, but in this challenge, you need to move 2 disks from any starting peg to any goal peg.

You will be given two numbers (from 1 to 3) as input - the starting peg, and the goal peg. Write a function that calculates how to move 2 disks from the starting peg to the goal peg. Print out the steps.

Output Format:
Print the peg to move from, an arrow "->", and the peg to move to. For example, to move from peg 1 to peg 3, print "1->3".

Print all the steps for a given case on its own line. Print a newline after each case.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Comments

  • Getting a stack overflow error but am not sure what is wrong.

    //your code here
        int c=0;
        if(a==0){
            System.out.println(a + " -> "+b);
    
        }
        else{
            doStuff(a,b);
            System.out.println(a + " -> "+b);
            doStuff(c,b);
        }
    
  • I don't know if this is how you thought for us to do it but this works for me.

    //your code here
    int notUsed = 0;
    for (int i = 1; i <= 3; i++){
    if(i != a && i != b){
    notUsed = i;
    }
    }
    System.out.println(a + "->" + notUsed + " " + a + "->" + b + " " + notUsed + "->" + b);

  • @Kevin: you never break the loop.
    Hint: never reduces a, so it will never reach 0 to break the loop

  • Hi my script is correct (as i was able to test the correct output using another browser)

    however im not clear on whats the submition rule for learneroo. Using javascript, does learneroo accept
    console.log(Start + "->" + End)?

    cont...
  • @Ed, just use print() to print in Javascript. I'm going to add more help info soon.

Contact Us