Towers of Hanoi - Part 1
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:
- Only one disk can be moved at a time.
- You can only move the top disc in a stack.
- 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
Kevin Guevara
Jun 2, 1:10 PMGetting a stack overflow error but am not sure what is wrong.
Zach
Sep 12, 10:56 AMI 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);
Peter Varsanyi
Sep 14, 11:45 AM@Kevin: you never break the loop.
Hint: never reduces a, so it will never reach 0 to break the loop
Ed Helms
Sep 14, 4:49 PMHi 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)?
here is my full recursion
function doStuff(a, b){
//your code here
// rule will be, 1st. move to the free peg.
// 2nd . move to the goal peg
// 3rd, move to the goal peg.
fp = 6-a-b;
Calc(2,a,fp,b);
}
//
Calc = function(n,Start,Mid,End){
if(n===0){
console.log (Start+"->" +End);
//document.write(Start+"->"+End);
};
Learneroo
Sep 14, 5:03 PM@Ed, just use
print()to print in Javascript. I'm going to add more help info soon.